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.

- Choose a reference date where the day of the week is known (e.g., 1st January 1971 was a Friday).
- Calculate the number of days between the reference date and the target date.
- 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.