Solution Explanation for LeetCode 1185: Day of the Week

This problem asks to find the day of the week for a given date. Several approaches exist, but the most efficient and commonly used method involves Zeller's Congruence. Alternatively, built-in date/time functionalities in various programming languages offer a simpler, albeit potentially less performant solution.

Approach 1: Zeller's Congruence

Zeller's Congruence is a formula that calculates the day of the week for any Gregorian calendar date. The formula is:

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

Where:

• w: Day of the week (0 = Sunday, 1 = Monday, ..., 6 = Saturday)
• c: Century (the integer part of the year divided by 100)
• y: Year of the century (year modulo 100)
• m: Month (3 = March, 4 = April, ..., 12 = December; January and February are treated as months 13 and 14 of the previous year, respectively)
• d: Day of the month
• ⌊⌋: Floor function (integer part)
• mod: Modulo operation

Algorithm:

1. Adjust Month and Year: If the month is January or February, adjust the month and year to treat them as months 13 and 14 of the previous year, respectively.
2. Calculate Components: Compute c and y from the input year.
3. Apply Zeller's Formula: Substitute the values into Zeller's congruence formula to calculate w.
4. Handle Negative Results: If w is negative, add 7 to make it positive.
5. Return Day Name: Use an array to map the calculated w value to the corresponding day of the week.

Time Complexity: O(1) - The algorithm performs a fixed number of calculations regardless of the input date. Space Complexity: O(1) - The algorithm uses a constant amount of extra space.

Approach 2: Using Built-in Date/Time Functions

Most programming languages provide built-in functions to handle dates and times. This approach leverages these functions for a more concise and readable solution. The trade-off is that it might be slightly less efficient than Zeller's congruence in some implementations.

Algorithm:

1. Create a Date Object: Create a date object using the input day, month, and year.
2. Get Day of Week: Use the language's built-in function to obtain the day of the week from the date object.
3. Return Day Name: Return the day name as a string.

Time Complexity: This varies depending on the language's implementation but is generally O(1) for efficient date/time libraries. Space Complexity: O(1) – Constant extra space is used.

Code Examples

The code examples below demonstrate both approaches using Python, Java, C++, Go and TypeScript. Approach 1 (Zeller's) is shown for all languages; Approach 2 (built-in functions) is shown only for Python and Java for brevity.

Approach 1 (Zeller's Congruence):

Python:

def dayOfTheWeek(day: int, month: int, year: int) -> str:
    days = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]
    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
    return days[w]
 

Java:

class Solution {
    public String dayOfTheWeek(int d, int m, int y) {
        String[] days = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        if (m < 3) {
            m += 12;
            y--;
        }
        int c = y / 100;
        y %= 100;
        int w = (c / 4 - 2 * c + y + y / 4 + 13 * (m + 1) / 5 + d - 1) % 7;
        return days[(w + 7) % 7]; // Handle negative w
    }
}

C++:

string dayOfTheWeek(int d, int m, int y) {
    string days[] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
    if (m < 3) {
        m += 12;
        y--;
    }
    int c = y / 100;
    y %= 100;
    int w = (c / 4 - 2 * c + y + y / 4 + 13 * (m + 1) / 5 + d - 1) % 7;
    return days[(w + 7) % 7];
}

Go:

func dayOfTheWeek(d int, m int, y int) string {
    days := []string{"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}
    if m < 3 {
        m += 12
        y--
    }
    c := y / 100
    y %= 100
    w := (c/4 - 2*c + y + y/4 + 13*(m+1)/5 + d - 1) % 7
    return days[(w+7)%7]
}

TypeScript:

function dayOfTheWeek(d: number, m: number, y: number): string {
    const days: string[] = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"];
    if (m < 3) {
        m += 12;
        y--;
    }
    const c: number = Math.floor(y / 100);
    y %= 100;
    const w: number = (Math.floor(c / 4) - 2 * c + y + Math.floor(y / 4) + Math.floor((13 * (m + 1)) / 5) + d - 1) % 7;
    return days[(w + 7) % 7];
}

Approach 2 (Built-in Date/Time Functions):

Python:

import datetime
 
def dayOfTheWeek(day: int, month: int, year: int) -> str:
    return datetime.date(year, month, day).strftime("%A")

Java:

import java.time.DayOfWeek;
import java.time.LocalDate;
 
class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        LocalDate date = LocalDate.of(year, month, day);
        DayOfWeek dayOfWeek = date.getDayOfWeek();
        return dayOfWeek.toString();
    }
}

Remember to handle potential errors like invalid dates (e.g., February 30th) appropriately in a production environment. The built-in function approach usually handles such errors gracefully by throwing exceptions. For Zeller's congruence, you would need explicit error handling.