Problem Description

You are given a date represented by three integers: day, month, and year. Your task is to determine which day of the week this date falls on.

The input consists of:

• day: An integer representing the day of the month (1-31)
• month: An integer representing the month (1-12)
• year: An integer representing the year

You need to return the name of the weekday as a string from the following set: {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

For example:

• If the input is day = 31, month = 8, year = 2019, you would return "Saturday" because August 31, 2019 was a Saturday.
• If the input is day = 18, month = 7, year = 1999, you would return "Sunday" because July 18, 1999 was a Sunday.

The problem requires you to implement a calendar calculation to map any valid date to its corresponding day of the week. The dates provided will be valid dates from the Gregorian calendar.

Intuition

When we need to find the day of the week for any given date, we're essentially trying to count how many days have passed since a known reference point and then determine which day of the week that count corresponds to.

The most straightforward approach is to leverage Python's built-in datetime module, which has already implemented the complex calendar calculations for us. The datetime.date() constructor creates a date object from the given year, month, and day, and the strftime('%A') method formats it to return the full weekday name.

However, if we were to implement this from scratch, we'd need a mathematical formula that accounts for:

• The cyclical nature of weeks (7 days repeating)
• The varying lengths of months
• Leap years and their effect on the calendar
• A known reference point (a date whose day of the week we know)

This is where Zeller's Congruence comes in - it's a mathematical algorithm that encodes all these calendar rules into a single formula. The formula cleverly handles:

• The irregular pattern of days in different months by using ⌊13(m+1)/5⌋
• Leap years through the year division terms ⌊c/4⌋ and ⌊y/4⌋
• The offset from a reference point through the constant adjustments

The key insight in Zeller's formula is treating January and February as months 13 and 14 of the previous year. This simplification moves the leap day (February 29) to the end of the counting year, making the mathematical pattern more regular.

The modulo 7 operation at the end gives us a number from 0 to 6, which maps directly to the days of the week, allowing us to return the corresponding day name from our array of weekday strings.

Learn more about Math patterns.

Solution Approach

The provided solution uses Python's built-in datetime module for a clean and simple implementation:

return datetime.date(year, month, day).strftime('%A')

However, let's walk through the mathematical approach using Zeller's Congruence, which is what the algorithm would use internally:

The formula is:

w = (⌊c/4⌋ - 2c + y + ⌊y/4⌋ + ⌊13(m+1)/5⌋ + d - 1) mod 7

Step-by-step implementation:

1. Adjust the month and year for Zeller's convention:

   • If the month is January (1) or February (2), treat it as month 13 or 14 of the previous year
   • This means: if month < 3, then month += 12 and year -= 1

2. Extract century and year components:

   • c = first two digits of year = year // 100
   • y = last two digits of year = year % 100

3. Apply the formula:

   • Calculate ⌊c/4⌋: This accounts for century leap years
   • Calculate -2c: This is the century adjustment
   • Add y: The year within the century
   • Calculate ⌊y/4⌋: This accounts for leap years within the century
   • Calculate ⌊13(m+1)/5⌋: This encodes the irregular month lengths
   • Add d: The day of the month
   • Subtract 1: Adjustment to align with the starting point
   • Take mod 7: This gives us a value from 0 to 6

4. Map the result to day names:

   • Create an array: ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
   • The result w directly indexes into this array

Example walkthrough for August 31, 2019:

• Initial values: day = 31, month = 8, year = 2019
• No adjustment needed since month > 2
• c = 20, y = 19
• w = (⌊20/4⌋ - 2×20 + 19 + ⌊19/4⌋ + ⌊13×9/5⌋ + 31 - 1) mod 7
• w = (5 - 40 + 19 + 4 + 23 + 31 - 1) mod 7
• w = 41 mod 7 = 6
• Result: "Saturday"

The Python datetime solution abstracts all this complexity while providing the same accurate result.

Example Walkthrough

Let's walk through finding the day of the week for July 18, 1999.

Using the datetime approach (simple solution):

datetime.date(1999, 7, 18).strftime('%A')  # Returns "Sunday"

Using Zeller's Congruence (mathematical approach):

Given: day = 18, month = 7, year = 1999

Step 1: Check if month adjustment is needed

• Since July (month = 7) is greater than 2, no adjustment needed
• Keep month = 7, year = 1999

Step 2: Extract century and year components

• Century: c = 1999 // 100 = 19
• Year within century: y = 1999 % 100 = 99

Step 3: Apply Zeller's formula

w = (⌊c/4⌋ - 2c + y + ⌊y/4⌋ + ⌊13(m+1)/5⌋ + d - 1) mod 7

Breaking down each term:

• ⌊c/4⌋ = ⌊19/4⌋ = 4 (century leap year adjustment)
• -2c = -2 × 19 = -38 (century adjustment)
• y = 99 (year within century)
• ⌊y/4⌋ = ⌊99/4⌋ = 24 (leap years within century)
• ⌊13(m+1)/5⌋ = ⌊13 × 8/5⌋ = ⌊104/5⌋ = 20 (month encoding)
• d = 18 (day of month)
• -1 (alignment adjustment)

Calculating the sum:

w = (4 - 38 + 99 + 24 + 20 + 18 - 1) mod 7
w = 126 mod 7
w = 0

Step 4: Map result to day name

• Days array: ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
• Index 0 corresponds to "Sunday"

Result: "Sunday" ✓

This matches our expectation that July 18, 1999 was indeed a Sunday!

Solution Implementation

Time and Space Complexity

The time complexity is O(1) because the datetime.date() constructor and strftime() method perform a fixed amount of operations regardless of the input values. The calculation to determine the day of the week involves mathematical operations (like Zeller's congruence or similar algorithms) that execute in constant time for any valid date input.

The space complexity is O(1) because the function only creates a single datetime.date object and returns a string representing the day of the week. The memory usage does not scale with the input size - it remains constant regardless of the specific day, month, or year values provided.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Manual Implementation Errors with Month Adjustment

When implementing Zeller's Congruence or similar algorithms manually, a frequent mistake is forgetting to adjust January and February to be treated as months 13 and 14 of the previous year. This leads to incorrect calculations.

Incorrect Implementation:

def dayOfTheWeek(day, month, year):
    # Wrong: Not adjusting January/February
    c = year // 100
    y = year % 100
    w = (c//4 - 2*c + y + y//4 + (13*(month+1))//5 + day - 1) % 7
    days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
    return days[w]

Correct Implementation:

def dayOfTheWeek(day, month, year):
    # Adjust for Zeller's convention
    if month < 3:
        month += 12
        year -= 1
  
    c = year // 100
    y = year % 100
    w = (c//4 - 2*c + y + y//4 + (13*(month+1))//5 + day - 1) % 7
    days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
    return days[w]

2. Incorrect Day Ordering in Manual Implementation

When creating the days array manually, developers might use a different starting day (like Monday instead of Sunday), causing off-by-one errors in the result.

Incorrect:

# Starting with Monday instead of Sunday
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"]

Correct:

# Zeller's formula returns 0 for Sunday, 1 for Monday, etc.
days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]

3. Integer Division vs Float Division

In Python 3, using regular division / instead of integer division // can cause floating-point results that lead to incorrect calculations.

Incorrect:

w = (c/4 - 2*c + y + y/4 + (13*(month+1))/5 + day - 1) % 7  # Uses float division

Correct:

w = (c//4 - 2*c + y + y//4 + (13*(month+1))//5 + day - 1) % 7  # Uses integer division

4. Negative Modulo Result Handling

In some programming languages, the modulo operation can return negative values for negative operands. This can cause index out of bounds errors when accessing the days array.

Solution:

# Ensure positive result
w = ((c//4 - 2*c + y + y//4 + (13*(month+1))//5 + day - 1) % 7 + 7) % 7

5. Not Validating Input Dates

The datetime approach will automatically raise an exception for invalid dates (like February 30), but manual implementations might produce incorrect results without validation.

Better approach with validation:

import datetime

def dayOfTheWeek(day, month, year):
    try:
        return datetime.date(year, month, day).strftime('%A')
    except ValueError:
        raise ValueError(f"Invalid date: {year}-{month:02d}-{day:02d}")

The datetime module approach elegantly avoids most of these pitfalls by handling all edge cases internally, making it the preferred solution for production code.