Tomohiko Sakamoto Algorithm

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

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:

  1. Consider January 1st 1 AD, which is a Monday as per Gregorian calendar.
  2. Now, first we take cases with no leap years. Here, total days would be 365.
  3. 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.
  4. This observations helps in determinig a common pattern that forms a base for this algorithm.
  5. 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}
  6. 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.
  7. 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.
  8. 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.
    1. The days[] array is {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}.
    2. if M corresponds to January or February (i.e., Month is less than 3),
      we decrement Y by 1.
    3. The annual increment inside the modulus is now Y + Y / 4 – Y / 100 + Y / 400
      in place of Y.

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.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.