Leetcode – Day of the Week Solution

Spread the love

The “Day of the Week” problem is an interesting problem on Leetcode that touches upon several programming and mathematical concepts including arrays, modulo arithmetic, and date manipulation. This problem may appear straightforward but it allows for several different approaches, each with its own set of trade-offs. In this article, we’ll dissect the problem, explore different solutions, and understand their time and space complexities.

Problem Statement

Description

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"}.

Constraints

  • The given dates are valid dates between the years 1971 and 2100.

Understanding the Problem

The problem asks us to determine the day of the week for a given date. One way to consider this problem is as a date manipulation task. The first step is to understand how dates relate to days of the week, which can be determined through various algorithms or formulae.

Approaches

Approach 1: Zeller’s Congruence Algorithm

Zeller’s Congruence is an algorithm devised by Christian Zeller to calculate the day of the week for any date. The formula for Zeller’s Congruence is:

Where:

  • h is the day of the week (0 = Saturday, 1 = Sunday, 2 = Monday, …)
  • q is the day of the month
  • m is the month (3 = March, 4 = April, 5 = May, …, 14 = February)
  • K is the year of the century (year mod  100)
  • J is the zero-based century

Python Code Implementation

def day_of_the_week(day, month, year):
    if month < 3:
        month += 12
        year -= 1

    K = year % 100
    J = year // 100

    f = day + ((13 * (month + 1)) // 5) + K + (K // 4) + (J // 4) + (5 * J)
    h = f % 7

    days = ["Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
    return days[h]

# Test the function
print(day_of_the_week(22, 8, 2023))  # Output should be "Tuesday"

Time Complexity

The time complexity for this approach is O(1).

Space Complexity

The space complexity for this approach is O(1).

Approach 2: Utilizing Python’s datetime Library

Python’s standard library provides a datetime module which can be used to solve this problem very efficiently.

Python Code Implementation

import datetime

def day_of_the_week(day, month, year):
    weekdays = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
    return weekdays[datetime.date(year, month, day).weekday()]

# Test the function
print(day_of_the_week(22, 8, 2023))  # Output should be "Tuesday"

Time Complexity

The time complexity for this approach is O(1).

Space Complexity

The space complexity for this approach is O(1).

Approach 3: Cumulative Days Approach

This approach involves calculating the total number of days that have passed since a known reference date and then using that information to determine the day of the week.

  1. Choose a reference date where the day of the week is known (e.g., 1st January 1971 was a Friday).
  2. Calculate the number of days between the reference date and the target date.
  3. Use modulo arithmetic to find the day of the week.

Python Code Implementation

def day_of_the_week(day, month, year):
    # Days in each month
    days_in_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    # Day names
    days = ["Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday"]
    
    # Count leap years that have passed
    def count_leap_years(y, m):
        if m <= 2:
            y -= 1
        return y // 4 - y // 100 + y // 400
    
    # Calculate total days since 1/1/1971
    total_days = day
    for i in range(1, month):
        total_days += days_in_month[i]
    total_days += (year - 1971) * 365 + count_leap_years(year, month)
    
    # Account for leap year
    if month > 2 and ((year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)):
        total_days += 1
    
    return days[total_days % 7]

# Test the function
print(day_of_the_week(22, 8, 2023))  # Output should be "Tuesday"

Time Complexity

The time complexity for this approach is O(1).

Space Complexity

The space complexity for this approach is O(1).

Conclusion

The “Day of the Week” problem serves as a great example to illustrate multiple approaches for solving what seems to be a simple problem. Each approach comes with its own set of advantages and disadvantages, but all of them have O(1) time and space complexity. Whether you’re using an established algorithm like Zeller’s Congruence, leveraging Python’s built-in libraries, or calculating days cumulatively, understanding the underlying principles can deepen your programming knowledge and problem-solving skills.

Leave a Reply