You are given the following information, but you may prefer to do some research for yourself.
- 1 Jan 1900 was a Monday.
- Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine. - A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
Solution
The most trivial solution to this problem would be to run over the full range of years and months and create a date object to retrieve the actual day of week to count all sundays. In JavaScript, this is as simple as
function solution() {
var n = 0;
for (var y = 1901; y <= 2000; y++) {
for (var m = 0; m < 12; m++) {
if (new Date(y, m, 1).getDay() === 0) {
n++;
}
}
}
return n;
} However, the actual work did someone else for us. So let's figure it out, how we can solve this problem by hand and maybe faster, since we don't really need a date object for every month of every year. One improvement could be to refer to Zeller's congruence, which is an algorithm to calculate the day of the week. For our Gregorian Calendar, this means:
\[ \begin{array}{rl} h=&\left(q+\left\lfloor {\frac {13(m+1)}{5}}\right\rfloor +K+\left\lfloor {\frac {K}{4}}\right\rfloor +\left\lfloor {\frac {J}{4}}\right\rfloor -2J\right){\bmod {7}}\\ =& \left(q+\left\lfloor {\frac {13(m+1)}{5}}\right\rfloor +K+\left\lfloor {\frac {K}{4}}\right\rfloor +\left\lfloor {\frac {J}{4}}\right\rfloor +5J\right){\bmod {7}} \end{array}\]
where
- h is the day of the week (0 = Saturday, 1 = Sunday, 2 = Monday, ..., 6 = Friday)
- q is the day of the month
- m is the month (3 = March, 4 = April, 5 = May, ..., 14 = February)
- K the year of the century (\(year \bmod 100\)).
- J is the zero-based century (actually \(year / 100\)) For example, the zero-based centuries for 1995 and 2000 are 19 and 20 respectively (to not be confused with the common ordinal century enumeration which indicates 20th for both cases).
function dow(y, m, q) {
var J = y / 100 | 0;
var K = y % 100;
// Map JavaScript zero-based month to Zeller's format
m = [13, 14, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12][m];
return (q + Math.floor(13 * (m + 1) / 5) + K + Math.floor(K / 4) + Math.floor(J / 4) + 5 * J) % 7;
} Plugging this new function into the solution() function above, and checking for 1 instead of 0 gives the same result. But again, we didn't do much work so far. As we know 1st Jan 1900 was a Monday and as we go sequentially through the dates, we can keep track of the day of week ourselves and just count the occurences of sundays. We also know that Februray is a problematic month, as it has leap years under the given condition. However, all this can be brought together to the following implementation:
function solution() {
var n = 0, dow = 2;
var months = [31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
for (var y = 1901; y <= 2000; y++) {
months[1] = 28 + (y % 4 === 0 && y % 100 !== 0 || y % 400 === 0);
for (var month of months) {
dow+= month % 7;
if (dow % 7 === 0) {
n++;
}
}
}
return n;
} But why does this work at all? If we know the first day, adding 7 days results in the same day of week and so on. As we go not day by day, but add the number days per month, we progress much faster. However, since we have 7 days per week and we're interested in one day exactly (Sunday), we sum under the modular congruence modulo 7, which means we can make use of homomorphic rule \((d+m) \equiv (d \bmod 7 + m \bmod 7) \pmod{7}\), which was then implemented here.