While I was searching for how to setup PHP on Mac, I found this guy's website (Jason) and his post in July. The problem he pointed out is:
Which year (only the last two digits) will have the most dates that satisfies the equation (day+month=year)?
For example, January 3, 2004
satisfies this (since 1+3=4
). So does February 2, 2004
. So in year 2004, for instance, how frequent this happens? The answer is 3, because we only have Jan. 3rd
, Feb. 2nd
, and Mar. 1st
.
In Jason's post, he did a simple test. And he found from year (20)13 to (20)30 have a maximum number 12.
The intuition here is that we only have 12 months. So if the sum is fixed, we can have a maximum of 12 occurrence here. Also, each month has only one day that satisfies the equation because d=y-m
is unique. Now, why from year 2013 to 2030?
Suppose the last two digits of the year is y
, the month is m
, and the day is d
. Then we want to find all m,d
pair such that y=m+d
, subjected to 0<m<13 and 0<d<32
if m=1,3,5,7,8,10,12
, 0<d<31
if m=4,6,9,11
, 0<d<29
if m=2
in non-leap years and 0<d<30
if m=2
in leap years. It seems like a long equation, but the idea just follows how many days in each month. And below is an analytical way to solve the equation.
We already know the max number of occurrence is 1 for each month. So for whatever y
, we want corresponding day d=y-m
exists in each month. The month numbers are fixed within 1 and 12. Since we know the smallest and largest day in each month, we just need to make sure every month has a day that satisfies y=m+d
. To do so, we need the year to be either the largest month adding the smallest day, or the min of largest possible day in all months adding that month. (This is sort of the idea of convolution.)
Therefore, Dec. 1st gives year (20)13 which is the lower bound. And since 28 from Feb. is the min of largest possible day in all months, we have year (20)30=28+2
, which is the upper bound. Since year (20)31 is not a leap year, we only have the range from year 2013 to 2030.
Thus, y=n%100
can be any number n
as long as:
(13 <= n%100 && n%100 <= 30) || (n%100 == 31 && isLeapYear(n))