LeetCode Solutions Blog

Day of the Week

Number: 1289

Difficulty: Easy

Paid? No

Problem Description

Given a specific date as day, month, and year, determine the day of the week that date falls on. The result must be one of: "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", or "Saturday." The input dates are guaranteed to be valid and within the range 1971 to 2100.

Key Insights

Use a reference date to compute the number of days elapsed until the given date.
January 1, 1971 is known to be a Friday.
Account for leap years properly for dates in February.
After obtaining the total number of days since the reference date, use modulo arithmetic to map the count into a weekday.

Space and Time Complexity

Time Complexity: O(Y) where Y is the number of years between 1971 and the given year (which is bounded by 2100, hence effectively constant). Space Complexity: O(1)

Solution

The approach is to compute the total number of days from January 1, 1971 (a known Friday) to the given date. For each complete year between 1971 and the given year, add 365 days, including an extra day for each leap year. Then, for the current year, add the days for the months before the given month (using 29 days for February in a leap year) and finally add the days within the month (subtracting one to account for the reference day).

Since January 1, 1971 is a Friday, we adjust the total days with an offset so that when the modulo by 7 is taken, it correctly maps to the weekday list ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]. Here, the offset is 5 because (0 days elapsed + 5) mod 7 yields 5, which corresponds to "Friday."

This solution uses simple arithmetic and conditional checks for leap years. It is efficient due to the bounded range of input years.

Code Solutions

# Python solution for the "Day of the Week" problem
def day_of_the_week(day, month, year):
    # List mapping index to day name (0 -> Sunday, 1 -> Monday, ..., 6 -> Saturday)
    day_names = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
    
    # Function to determine if a given year is a leap year
    def is_leap(year):
        # A year is leap if divisible by 400, or divisible by 4 but not by 100
        return (year % 400 == 0) or (year % 4 == 0 and year % 100 != 0)
    
    # Days in each month (for non-leap years)
    days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    
    # Starting from 1971-01-01 which is a Friday.
    total_days = 0
    
    # Add days for full years from 1971 up to (but not including) the current year
    for current_year in range(1971, year):
        total_days += 366 if is_leap(current_year) else 365

    # Add days for previous full months in the current year
    for current_month in range(1, month):
        if current_month == 2 and is_leap(year):
            total_days += 29  # February in a leap year
        else:
            total_days += days_in_month[current_month - 1]
    
    # Add days in the current month (subtract 1 because Jan 1, 1971 is day 0)
    total_days += (day - 1)
    
    # Since Jan 1, 1971 was a Friday, and in our day_names array "Friday" is at index 5,
    # we add an offset of 5 before taking modulo 7.
    week_day_index = (total_days + 5) % 7
    
    return day_names[week_day_index]

# Example usage:
print(day_of_the_week(31, 8, 2019))  # Output: Saturday
print(day_of_the_week(18, 7, 1999))  # Output: Sunday
print(day_of_the_week(15, 8, 1993))  # Output: Sunday