Problem 19 : Counting Sundays

Counting Sundays

Problem 19

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)?

                                                                                                       (https://projecteuler.net/problem=19)
Now we are on the problem with calendar counting.

I have always hoped that our current calendar becomes simpler and more uniform (without any confusing leap years and varying month lengths, ... etc), but, whatever.

At least it makes calendar counting problems more fun and exciting, so I'm ok with it now.

We are dating back to January 1st, 1901, when 20^th century began.

Here are some important events in 1901.

Ok. Let's start writing our algorithm.

First method that I want is to determine if the year is leap year or not.

Because leap years are divisible by 4, but centuries don't count, but 400-multiple centuries do count, it seems tedious, and we need several steps.

public static boolean isLeap(int y)

{...}

So first filter is whether the year is multiple of 4; if it is, then that year can be leap year possibly; if not, then no chance.

if (y%4 == 0)
{
    ...
}
return false;

Second, if the year is divisible by 4, then we check if the year is multiple of 400; if it is, then it is a leap year; if not, then we'll see.

if (y%4 == 0)
{
    if (y%400 == 0) return true;
    else ...
}

Third, if the year isn't multiple of 400, then we check if the year is multiple of 100; if it is. then it is not a leap year; if not, it is.

if (y%4 == 0)
{
    if (y%400 == 0) return true;
    else if (y%100 == 0) return false;
    return true;
}

When we combine them:

public static boolean isLeap(int y)
{
    if (y%4 == 0)
    {
        if (y%400 == 0) return true;
        else if (y%100 == 0) return false;
        return true;
    }
    return false;
}

After making that method, I worked on how to easily find out Sundays without using complicated algorithms involving arrays or Strings.

So here is the system that I designed, and it worked perfectly:

S	M	T	W	T	F	S
0	1	2	3	4	5	6

Using divisibility by 7, we can get the reminders from 0-6.

if the day count divided by 7 gives us 1, then we know that it is Monday.

For example, starting with Monday, we want to know what day it is after 24 days.

Because Monday is 1 in the chart, and 1 + 24 = 25, we divide it by 7, and we will get 4 as a reminder.

And 4 is Thursday, according to the chart I made. Ah! It is Thursday after 24 days.

My algorithm is the Modulus Representation of Days (Modulo 7).

From now on, it becomes really easy implementation.

We start with 0 Sunday count, and day 2 (which is Tuesday, according to the chart I made):

int count = 0, day = 2;

Year from 1901 to 2000 and month from 1 to 12:

for (int y = 1901; y <= 2000; y++) // years
{
    for (int m = 1; m <= 12; m++) // months
    {
        ...
    }
    ...
}

If months are April, June, September, and November, there are 30 days always:

if (m == 4 || m == 6 || m == 9 || m == 11)
    day += 30;

If February, then we check leap-year-ity of the year:

else if (m == 2)
{
    if (isLeap(y)) day += 29;
    else day += 28;
}

Rest of the months are 31 days:

else day += 31;

After that, we divide by 7 and get the reminder. If the reminder is 0 on the first day of each month, we know that it is Sunday:

day %= 7;
if (day == 0) count++; // if it is sunday

Combining all that:

int count = 0, day = 2; // modulus representation of days (modulo 7) : SMTWTFS == 0123456
  
for (int y = 1901; y <= 2000; y++) // years
{
    for (int m = 1; m <= 12; m++) // months
    {
        if (m == 4 || m == 6 || m == 9 || m == 11)
            day += 30;
        else if (m == 2)
        {
            if (isLeap(y)) day += 29;
            else day += 28;
        }
        else day += 31;
  
        day %= 7;
        if (day == 0) count++; // if it is sunday
    }
}
System.out.println(count);

Answer is 171
Execution time is .796564 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem019.java