I have read a formula to determine the difference between two date using math with O(1) time complexity
365*year + year/4 - year/100 + year/400 + (153*month - 457)/5 + day - 306
with considering
if month number less than 3 , year-=1 and month+=12
the following link show the whole code which i quote from
https://codeforces.com/contest/304/submission/3715756
So if someone can explain it please ?
This is not a full answer but it is some explanation.
First of all the
if month number less than 3 , year-=1 and month+=12
is used to effectively start the year from March moving the highly irregular February to the end. Actually this is how this calendar was originally designed which you still can see in the names of some month like October or December (you probably hear that Oct = 8 and Dec = 10).
The 365*year + year/4 - year/100 beat is just handling the leap years.
The day part is also clear.
Now let's remove the bits that are irrelevant when we subtract two values and get this value for month
30*month + (3*month - 2)/5
I don't know the logic how it was got (I only have a guess at the end) but I can say why it works. The 30*month bit is obvious. And now when we moved the February to its last position, all the month in the middle of the year have either 30 or 31 day. Let's write them down:
We don't care about February as there are no months after it (we cared about that before). We only care about this +1 day since the next month after that!
So what we need now is some formula that would match that distribution of +1 and +0. And it appears that the value
(3*month - 2)/5
with integer division does exactly that. You can easily verify it by hand.
Probably the way to come up with this idea was to notice that the year (except for February) follows the following 5-month-cycle
+1 +0 +1 +0 +1
I mean March-July and August-December both match it exactly and then January is again +1 so it is like the first element of the next cycle.