Difficulty: Easy | Acceptance: 59.10% | Paid: No Topics: Math
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 Saturday.
- Examples
- Constraints
- Built-in Library Functions
- Zeller’s Congruence
- Reference Date Calculation
Examples
Input: day = 31, month = 8, year = 2019
Output: "Saturday"
Input: day = 18, month = 7, year = 1999
Output: "Sunday"
Input: day = 15, month = 8, year = 1993
Output: "Sunday"
Constraints
1971 <= year <= 2100
1 <= month <= 12
1 <= day <= number of days in the specific month
Built-in Library Functions
Intuition Most modern programming languages provide built-in libraries for date and time manipulation. These libraries internally handle the complexities of the Gregorian calendar, including leap years, allowing us to determine the day of the week with a single function call.
Steps
- Create a date object using the provided year, month, and day.
- Use the library’s formatting or getter function to extract the day of the week.
- Return the result as a string.
import datetime
class Solution:
def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]
d = datetime.date(year, month, day)
return days[d.weekday()]Complexity
- Time: O(1)
- Space: O(1)
- Notes: Relies on standard library optimizations.
Zeller’s Congruence
Intuition Zeller’s Congruence is an algorithm devised by Christian Zeller to calculate the day of the week for any Julian or Gregorian calendar date. It uses a mathematical formula to map the date to a number corresponding to the day of the week.
Steps
- Adjust the month and year: if the month is January or February, treat it as month 13 or 14 of the previous year.
- Apply Zeller’s formula:
h = (q + floor(13(m+1)/5) + K + floor(K/4) + floor(J/4) + 5J) mod 7. - Map the result $h$ to the corresponding day name (0=Saturday, 1=Sunday, etc.).
class Solution:
def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
if month < 3:
month += 12
year -= 1
c = year // 100
y = year % 100
# Zeller's Congruence
w = (day + (13 * (month + 1)) // 5 + y + y // 4 + c // 4 + 5 * c) % 7
days = ["Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
return days[w]Complexity
- Time: O(1)
- Space: O(1)
- Notes: Constant time mathematical calculation.
Reference Date Calculation
Intuition We can calculate the total number of days elapsed from a known reference date (e.g., January 1, 1971, which was a Friday) to the target date. The day of the week is then determined by the remainder when this total is divided by 7.
Steps
- Define the number of days in each month, accounting for leap years.
- Iterate through the years from the reference year to the target year, adding 365 or 366 days depending on whether it is a leap year.
- Iterate through the months of the target year, adding the days for each month.
- Add the remaining days of the current month.
- Calculate the offset from the reference day and return the corresponding day name.
class Solution:
def dayOfTheWeek(self, day: int, month: int, year: int) -> str:
days = ["Friday", "Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday"]
month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
def is_leap(y):
return y % 400 == 0 or (y % 4 == 0 and y % 100 != 0)
total_days = 0
# Count days from 1971 to year - 1
for y in range(1971, year):
total_days += 366 if is_leap(y) else 365
# Count days from Jan to month - 1
for m in range(1, month):
if m == 2 and is_leap(year):
total_days += 29
else:
total_days += month_days[m - 1]
total_days += day
return days[total_days % 7]Complexity
- Time: O(1) (Since the year range is bounded by 1971-2100, the loop runs a maximum of ~130 times).
- Space: O(1)
- Notes: More logic than Zeller’s but easy to understand.