Get this book -> Problems on Array: For Interviews and Competitive Programming

The Tomohiko Sakamoto Algorithm is used to find the Day of the week for a given date. The date is provided according to the Gregorian Calendar.

**Sample Input and Output format**

```
Input : 09 09 2020 (9th September 2020)
Output : 3 (i.e Wednesday)
Input : 15 08 2012 (15th August 2012)
Output : 3 (i.e Wednesday)
Input : 24 12 2456 (24th December 2046)
Output : (0 i.e Sunday)
```

**Algorithm Explanation/Steps with example:**

- Consider January 1st 1 AD, which is a Monday as per Gregorian calendar.
- Now, first we take cases with no leap years. Here, total days would be 365.
*January*has 31 days i.e 7 * 4 + 3 days so the day on*1st February*will always be 3 days ahead of the day on*1st January*. Now,*February*has 28 days(if we do not include leap years) which is an exact multiple of 7 (7 * 4 = 28). So, there will be no change in the month of*March*and it will also be 3 days ahead of the day on*1st January*of that respective year.- This observations helps in determinig a common pattern that forms a base for this algorithm.
- We will create an array for the leading number of days of
*each*month, it will be given as days[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5} - Now we consider cases of leap years. Every
*4 years*, our calculation will gain*one extra*day. Except every 100 years when it will not. We need to calculate these extra days also. We will add Y / 4 β Y / 100 + Y / 400 which exactly the required number of leap years. But, there is an exception. - The leap day is
*29 February*and not*0 January*which implies that the current year should not be counted for the leap day calculation for the first two months. Suppose that if the month were*January*or*February*, we subtracted 1 from the year. This means that during these months, the Y / 4 value would be that of the previous year and would not be counted. - If we subtract 1 from the days[] values of every month after
*February*, then the gap would fill, and the issue is solved in the case of a leap year. We add the following changes to make the algorithm work for both*leap*and*non-leap*years.- The
*days[]*array is {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}. - if M corresponds to
*January*or*February*(i.e., Month is less than 3),

we decrement Y by 1. - The annual increment inside the modulus is now Y + Y / 4 β Y / 100 + Y / 400

in place of Y.

- The

```
public class Tomohiko_Sakamoto_Algorithm {
private static int day_of_the_week(int Y, int M, int D) {
int days[] = new int[] { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
if (M < 3)
Y--;
return (Y + Y / 4 - Y / 100 + Y / 400 + days[M - 1] + D) % 7;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Please enter Day of Date");
int Day = scan.nextInt();
System.out.println("Please enter Month of Date");
int Month = scan.nextInt();
System.out.println("Please enter Year of Date");
int Year = scan.nextInt();
System.out.println("It was " + day_of_the_week(Year, Month, Day) + " on the given date");
System.out.println();
}
}
```

**Notes:**

The **Time** **Complexity** for the above program is *O(1)*.

This algorithm is very fast in calculating the Day for a given date. There are many more algorithms available for finding the Day, but this algorithm is very less known and is among the most efficient ones.