Get insightful articles from the world of tech recruiting. Straight to your inbox.

Here's what you can do next

Check out FaceCode:
an intelligent coding interview tool

Learn More
Algorithm on how to find the day of a week
How to calculate the day of a week

 

In 1970, John Horton Conway came up with an algorithm, often termed the “Doomsday Algorithm.” (Though it had no relation to December 21, 2012 — the predicted doomsday) to quickly calculate the day of a week without resorting to anything but a few calculations in your head. (It is easy to memorize, so don’t fret.)

This algorithm uses the formula: (d+m+y+[y/4]+c ) mod 7

Where d is the day, m is the month addressed in the date, y is the calendar year, and c is the century number.

Each day of the week is given a number. For instance, Sunday is the first day of the week and is represented by 1, Monday by 2, and so on. In a few calendars, the week begins with 1 as for Monday and 7 as Sunday, which is like the ISO 8601 standards calendar. These numbers are achieved using Modulo 7.

What do we know?

We know that every year has 365 days (Except the leap year which has 366 days). Every week has 7 days. Every month has 30 or 31 days except February which has 28 days in a common calendar year and 29 days in a leap year.

Since 365 mod 7= 1, every year starts from the next day it’s from the day its preceding year started. So if January 1, 2001, was Monday, January 1, 2002, will fall on a Tuesday because 2002 was not a leap year.

Though 11 months of a year have 30 or 31 days, some months begin exactly on the same day as some other month.

Let’s take an example.

April 2016 starts on Friday, so does July 2016. How? April has 30 Days, May 31 days, and June has 30 days, which add up to 91.

91 modulo 7= 0, which returns a remainder of zero. Hence, July starts the same day as April does.

Determination of day of week, How to calculate day of a week, Common months in an year,Algorithm on how to find the day of a week,algorithm for finding the day you were born

The good news is that we have a bunch of months that start on the same day as some other month of the year.
For common years:
January and October
February, March, and November
April and July
No month corresponds with August

Corresponding month in common year, Determination of day of week, How to calculate day of a week, algorithm for finding the day you were born

 

For leap years:
January, April, and July
February and August
March and November
No month corresponds with October

images_1-03

 

 

Following these algorithms, Tomohiko Sakamoto developed an algorithm using the formula above for the determination of a day of a week, which also took into consideration the additional day in a leap year.

Let’s see how Tomohiko Sakamoto’s used the Doomsday Algorithm to determine the day of the week.

January has 31 days, which if divided into a week of 7 days will give 7 ? 4 + 3 days, hence we know that February 1 will be 3 days following the day that was January 1.

Similarly, 31 days of January + 28 days of February = 59 days, which is equal to 7 ? 8 +3, and it makes sense when we say that March 1 will fall 3 days following the day that was January 1.

Thus, we get a subset of each month corresponding to January 1 {0,3,3,6,1,4,6,2,5,0,3,5}, where the first day of the month is represented by a number in the subset.

Now 365 days make a year, which is 7 ? 52 + 1.

This addition of an extra day every year is adjusted every 4 years as a leap year, that is, February 29th.

So, every 4 years, the Gregorian calendar gains one extra day.

Which it doesn’t after 100 years and as the calendar repeats every 400 years, it again gains an extra day in the 400th year.

Why do they have to make it so complicated?

To put things mathematically, we add an additional day as y/4 – y/100 + y/400.

Considering the rules above, which work for all calendars for a leap year, we must divide a year by 4 to see if it is a leap year. But 100, though divisible by 4, can’t be a leap year, so you subtract year/100. As mentioned, every 400 years it would be a leap year, hence add year/400. With all the addition and subtraction, we accurately add that one day to the leap year.

Good, so we have mathematically adjusted the leap year. Not so difficult, right?

But the extra day comes in the month of February and not January.

We subtract a day from the first two months to make the algorithm work:
y -= m < 3

As we numbered the months from 1 to 12, for every month which has a value less than 3, which in our case would be January and February, subtract 1 from its original value so January becomes 0 and February become 1.

But doing this deletes a day from February and January even during non-leap years, which leaves a blank day between February end and March 1. To avoid it, let’s subtract a day from each month from March to December, making the list look like this:

{0,3,2,5,0,3,5,1,4,6,2,4}

The following codes will give Monday as 1 and Sunday as 7:

This finally gives us the following C++ code:

int dow(int y, int m, int d)
{
  static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
  y -= m < 3;
  return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}

Here is a Python Code for the Algorithm

def day_of_week(year, month, day):
	t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
	year -= month < 3
	return (year + int(year/4) - int(year/100) + int(year/400) + t[month-1] + day) % 7

I may not achieve Iron Man status in their minds, but it is a start.

 

 

Algorithms Developers

Empowering developers at HackerEarth | Fascinated with Recruiting, Candidate Experience, Branding | Digital Marketing | LinkedIn connections are awesome (Just saying!)

Here's what you can do next

Check out FaceCode:
an intelligent coding interview tool