Day Of The Week - Leetcode Solution

Problem Statement:

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month, and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

Solution:

Approach 1: Using Built-In Libraries

We can use built-in libraries like datetime module in Python to solve this problem. We can create a datetime object from the given date and then get the weekday() method which returns the day of the week as a integer where Monday is 0 and Sunday is 6. We can use this integer to get the corresponding day of the week from the list of days given.

Time Complexity: O(1) Space Complexity: O(1)

Python Code:

import datetime

class Solution:
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
        return days[datetime.date(year, month, day).weekday()]

Approach 2: Using Zeller's Congruence Algorithm

Zeller's Congruence algorithm is a mathematical formula used to find the day of the week for any given date. This algorithm is based on the idea that the day of the week is a function of the day, month, and year, and that each of these values can be expressed as a set of congruences or remainders.

Zeller's Congruence Algorithm:

1. If the month is January or February, replace it with the months 13 and 14 of the previous year, respectively.

2. Compute the year of the century (year modulo 100).

3. Divide the year by 100 to get the century number.

4. Divide the day by 7 and calculate the remainder.

5. Calculate the year remainder, century remainder, and month adjustment values using the formulas:

   • year remainder = year % 100
   • century remainder = year // 100
   • month adjustment = (13*month + 8)//5

6. Calculate the day of the week using the formula:

   • day of the week = (day + month adjustment + year remainder + year remainder // 4 + century remainder // 4 + 5*century remainder) % 7

   • The result of this formula is an integer from 0 to 6, representing the day of the week where Sunday is 0 and Saturday is 6.

7. Map the integer result to the corresponding day of the week from the list of days given.

Time Complexity: O(1) Space Complexity: O(1)

Python Code:

class Solution:
    def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
        
        days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
        
        if month < 3:
            month += 12
            year -= 1
            
        year_rem = year % 100
        century = year // 100
        month_adjust = (13*month + 8) // 5
        
        day_of_week = (day + month_adjust + year_rem + year_rem // 4 + century // 4 + 5*century) % 7
        
        return days[day_of_week]

1