Tomohiko Sakamoto's algorithm - finding the day of the week

In this article, we will discuss what the Tomohiko Sakamoto algorithm is and how to use it to identify which day of the week a given date is. There are several algorithms to know the day of the week, but this algorithm is the most powerful one. This algorithm finds the day of the month in which this date occurs in the smallest possible time and with the smallest space complexity.

Problem Statement - We are given a date based on the Georgian calendar and our task is to find out which day of the week the given date is using Tomohiko Sakamoto's algorithm.

Example

Input - Date = 30, Month = 04, Year = 2020

Output - The given date is Monday

Input - Date = 15, Month = 03, Year = 2012

Output - The given date is Thursday

Input - Date = 24, Month = 12, Year = 2456

Output - The given date is Sunday

Sakamoto Tomohiko’s algorithm

Now let’s discuss the intuition behind Sakamoto Tomohiko’s algorithm.

As we all know, according to the Georgian calendar, January 1 AD falls on a Monday.

Case 1 Ignore leap years

We first discuss the case where all leap years are ignored, i.e. there are 365 days in a year.

Since January has 31 days and a week has 7 days, we can say that January has 7*4 3 days, which means the first day of February is always 3 days after the first day of January. p>

Since February has 28 days (except for leap years), which itself is a multiple of 7, we can say that March 1st will be on the same day as February 1st, which means that March 1st will also be 3 1 The number of days after the 1st of the month.

Now, for April, March has 31 days, which is 7*4 3, which means it will happen 3 days after March 1st. Therefore, we can say that April 1st will occur 6 days after January 1st.

We will now construct an array where arr[i] represents the number of additional days after month i occurs relative to January 1st.

We have arr[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}.

Case 2 Leap Year

Now let’s discuss the leap year situation.

Every four years, a day is added to our calculations, but not every hundred years. We have to account for these extra days. To do this we will use the formula -

Years / 4 (every 4 years)

– Year / 100 (for every 100 years that is a multiple of 4 but still not a leap year, we remove it from the leap year)

Year / 400 (every 400th year, it is a multiple of 100, but still a recurring year)

This formula will give us the exact number of leap years. However, there is one exception.

Now, we know that February 29th is considered a leap day, not January 0th.

This means that we do not need to include the first two months of the year in the calculation, as leap days have no effect on them. So if it's January or February, we'll subtract 1 from the year to compensate. Therefore, in these months, the value of year/4 should be based on the previous year rather than the current year.

To solve the leap year problem, we can subtract 1 from the arr[] value for each month after February to fill in the gaps. This solves the leap year problem. We need to make the following changes to the algorithm so that it works in both leap years and flat years.

arr[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 }

If the current month is January or February, we need to subtract 1 from the year.

We need to modify the year increment in the modulus to year year/4 –year/100 year/400 instead of year. This change is necessary to account for the extra day in a leap year and adjust the calculations accordingly.

Example

The code for this method is:

#include <bits/stdc++.h>
using namespace std;
// code to find out the day number of the given date
int Weekday(int year, int month, int day) {
   int arr[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
	
   if ( month < 3 )
      year -= 1;
   return ( ( year + year / 4 - year / 100 + year / 400 + arr[month - 1] + day) % 7 );
}

int main(void) {
   int day = 9, month = 9, year = 2020;
   int d = Weekday(year, month, day);
   string days[] = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" };
   cout<< " The given date is on "; 
   cout << days[d];
   return 0;
}

Output

The given date is on Wednesday

Complexity

Time complexity - The time complexity of this method is O(1)

Space Complexity - The space complexity of this approach is O(1) since we are not using any extra space.

Conclusion - In this article we discussed Tomohiko Sakamoto’s algorithm and the intuition behind it

The above is the detailed content of Tomohiko Sakamoto's algorithm - finding the day of the week. For more information, please follow other related articles on the PHP Chinese website!