Jobs

Interviews

Discussions

Day of the Week

Easy

Asked by:

12 views

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

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"

Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"

Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

Constraints:

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

Try coding it in LeetCode

Day of the Week

Easy

Asked by:

12 views

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

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"

Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"

Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected input format? Specifically, are the dates provided as strings, and if so, what is the string format? Or are the dates given as a day, month, and year separately?
What is the valid range for the year? Is there a minimum or maximum year I should consider?
Are the day, month, and year guaranteed to form a valid date within the given range?
Should the return value be the full day of the week (e.g., "Sunday") or an abbreviation (e.g., "Sun")?
Is the Gregorian calendar the only calendar system to consider? Or do I need to account for potential variations or historical calendar changes?

Brute Force Solution

Approach

The goal is to find the day of the week for a given date. With a brute force approach, we'll simply count forward or backward from a known date (like January 1, 1971, which was a Friday) one day at a time until we reach the target date, keeping track of which day of the week we're on.

Here's how the algorithm would work step-by-step:

Start with a known date and its corresponding day of the week. Let's say we know January 1, 1971 was a Friday.
Calculate the difference in days between the target date and the known date.
If the target date is after the known date, move forward one day at a time, updating the day of the week as you go (Friday becomes Saturday, Saturday becomes Sunday, etc.).
If the target date is before the known date, move backward one day at a time, updating the day of the week as you go (Friday becomes Thursday, Thursday becomes Wednesday, etc.).
For each day you move, make sure to account for the different number of days in each month and leap years when needed.
Repeat this process until you reach the target date.
The day of the week you've arrived at is the answer.

Code Implementation

def day_of_the_week(day, month, year):
    known_year = 1971
    known_day_of_week = 4  # Friday

    days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

    total_days = 0

    # Calculate days from 1971 to the given year
    for current_year in range(known_year, year):
        if is_leap_year(current_year):
            total_days += 366
        else:
            total_days += 365

    # Add days for the months in the given year
    for current_month in range(month - 1):
        total_days += days_in_month[current_month]
        if is_leap_year(year) and current_month == 1:
            total_days += 1

    total_days += day - 1

    # Adjust for the known day of the week
    day_index = (known_day_of_week + total_days) % 7

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

def is_leap_year(year):
    # Account for leap years
    if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
        return True
    return False

Big(O) Analysis

Time Complexity

O(n) – The dominant operation is calculating the difference in days between the target date and the known date. In the worst-case scenario, the target date could be many years away from the known date, requiring us to iterate day by day until we reach the target. The number of iterations is directly proportional to the number of days 'n' between the dates. Therefore, the time complexity is O(n), where n represents the number of days between the start and end dates.

Space Complexity

O(1) – The algorithm described in the plain English explanation operates by iteratively incrementing or decrementing dates and updating the day of the week. It doesn't involve any auxiliary data structures like arrays, hash maps, or lists to store intermediate results. The space used is limited to storing a few variables like the current date, the day of the week, and the known date. Therefore, the space complexity is constant and independent of the input date, resulting in O(1) space complexity.

Optimal Solution

Approach

The best way to find the day of the week for any given date involves using a known formula that efficiently calculates the day based on the date's components. Instead of counting day by day from a known date, this formula leverages mathematical properties to jump directly to the solution. We need to break down the date into year, month, and day components and apply the magic formula.

Here's how the algorithm would work step-by-step:

First, remember that months are numbered 1 to 12 but that the formula might treat January and February a little differently, assigning them to the previous year as the 13th and 14th months, respectively. This avoids edge cases in the formula.
Next, adjust the year if we've re-labeled January or February. We subtract 1 from the year in this case.
Now, apply the formula. The formula typically involves adding the day, a value derived from the month, the last two digits of the year, the last two digits of the year divided by 4, the century divided by 4, and subtracting twice the century (or some similar calculation).
After doing the calculation, find the remainder when dividing the sum by 7. This remainder represents the day of the week where 0 could be Sunday, 1 could be Monday, and so on.
Finally, use the remainder to lookup the corresponding day of the week in a predefined list or array.
This approach gets us the answer quickly without brute-force calculation because it's based on mathematical patterns in the calendar.

Code Implementation

def day_of_the_week(day, month, year):
    day_list = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]

    # Adjust month and year for Jan/Feb
    if month < 3:
        month += 12
        year -= 1

    year_of_century = year % 100
    century = year // 100

    # Zeller's Congruence formula
    # This formula is the core logic for calculating the day
    day_index = (day + (13 * (month + 1)) // 5 + year_of_century + (year_of_century // 4) + (century // 4) - (2 * century)) % 7

    # Python's modulo can return negative numbers, so adjust.
    day_index = (day_index + 7) % 7

    # Return the day of the week
    return day_list[day_index]

Big(O) Analysis

Time Complexity

O(1) – The provided solution uses a formula to calculate the day of the week, which involves a fixed number of arithmetic operations regardless of the input date. These operations include additions, divisions, and modulus operations. Since the number of operations does not depend on the size of any input variable, the time complexity is constant.

Space Complexity

O(1) – The algorithm uses a fixed amount of extra memory. It stores the day, month, year components, and a few integer variables for the calculation and the final remainder. These variables occupy constant space, independent of the input date. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Invalid date components (e.g., month 0, day 0, year -1)	Handle invalid date components by either returning an error message or defaulting to a sensible default date (e.g., January 1, 1900) and documenting the behavior.
Dates outside the range supported by the algorithm (e.g., before the Gregorian calendar was adopted)	Check if the input date is within the supported range and return an error or a predefined result if outside.
Leap years and their impact on the day of the week calculation, especially around February 29th	Ensure the algorithm correctly accounts for leap years by incorporating leap year logic in the date calculations.
Dates close to integer limits (potential overflow during calculations)	Use appropriate data types (e.g., long) and modular arithmetic to prevent integer overflow during calculations.
Ambiguous date formats (e.g., mm/dd/yyyy vs dd/mm/yyyy)	Specify the expected date format and validate the input accordingly, returning an error if the format is incorrect.
Epoch year is a leap year (Year 0000 being invalid)	Do not assume year 0 to be a valid leap year, and use the correct offset to calculate the Julian day.
Gregorian calendar reform date	If the algorithm spans dates before and after the Gregorian reform, incorporate logic to handle the change in calendar systems.
Very large year values that could introduce precision errors or performance issues	Ensure that the algorithm handles large year values gracefully without introducing precision errors or performance degradation.

Invalid date components (e.g., month 0, day 0, year -1)

How to Handle:

Handle invalid date components by either returning an error message or defaulting to a sensible default date (e.g., January 1, 1900) and documenting the behavior.

Dates outside the range supported by the algorithm (e.g., before the Gregorian calendar was adopted)

How to Handle:

Check if the input date is within the supported range and return an error or a predefined result if outside.

Leap years and their impact on the day of the week calculation, especially around February 29th

How to Handle:

Ensure the algorithm correctly accounts for leap years by incorporating leap year logic in the date calculations.

Dates close to integer limits (potential overflow during calculations)

How to Handle:

Use appropriate data types (e.g., long) and modular arithmetic to prevent integer overflow during calculations.

Ambiguous date formats (e.g., mm/dd/yyyy vs dd/mm/yyyy)

How to Handle:

Specify the expected date format and validate the input accordingly, returning an error if the format is incorrect.

Epoch year is a leap year (Year 0000 being invalid)

How to Handle:

Do not assume year 0 to be a valid leap year, and use the correct offset to calculate the Julian day.

Gregorian calendar reform date

How to Handle:

If the algorithm spans dates before and after the Gregorian reform, incorporate logic to handle the change in calendar systems.

Very large year values that could introduce precision errors or performance issues

How to Handle:

Ensure that the algorithm handles large year values gracefully without introducing precision errors or performance degradation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected input format? Specifically, are the dates provided as strings, and if so, what is the string format? Or are the dates given as a day, month, and year separately?
What is the valid range for the year? Is there a minimum or maximum year I should consider?
Are the day, month, and year guaranteed to form a valid date within the given range?
Should the return value be the full day of the week (e.g., "Sunday") or an abbreviation (e.g., "Sun")?
Is the Gregorian calendar the only calendar system to consider? Or do I need to account for potential variations or historical calendar changes?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a known date and its corresponding day of the week. Let's say we know January 1, 1971 was a Friday.
Calculate the difference in days between the target date and the known date.
If the target date is after the known date, move forward one day at a time, updating the day of the week as you go (Friday becomes Saturday, Saturday becomes Sunday, etc.).
If the target date is before the known date, move backward one day at a time, updating the day of the week as you go (Friday becomes Thursday, Thursday becomes Wednesday, etc.).
For each day you move, make sure to account for the different number of days in each month and leap years when needed.
Repeat this process until you reach the target date.
The day of the week you've arrived at is the answer.

Code Implementation

def day_of_the_week(day, month, year):
    known_year = 1971
    known_day_of_week = 4  # Friday

    days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

    total_days = 0

    # Calculate days from 1971 to the given year
    for current_year in range(known_year, year):
        if is_leap_year(current_year):
            total_days += 366
        else:
            total_days += 365

    # Add days for the months in the given year
    for current_month in range(month - 1):
        total_days += days_in_month[current_month]
        if is_leap_year(year) and current_month == 1:
            total_days += 1

    total_days += day - 1

    # Adjust for the known day of the week
    day_index = (known_day_of_week + total_days) % 7

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

def is_leap_year(year):
    # Account for leap years
    if year % 4 == 0 and (year % 100 != 0 or year % 400 == 0):
        return True
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, remember that months are numbered 1 to 12 but that the formula might treat January and February a little differently, assigning them to the previous year as the 13th and 14th months, respectively. This avoids edge cases in the formula.
Next, adjust the year if we've re-labeled January or February. We subtract 1 from the year in this case.
Now, apply the formula. The formula typically involves adding the day, a value derived from the month, the last two digits of the year, the last two digits of the year divided by 4, the century divided by 4, and subtracting twice the century (or some similar calculation).
After doing the calculation, find the remainder when dividing the sum by 7. This remainder represents the day of the week where 0 could be Sunday, 1 could be Monday, and so on.
Finally, use the remainder to lookup the corresponding day of the week in a predefined list or array.
This approach gets us the answer quickly without brute-force calculation because it's based on mathematical patterns in the calendar.

Code Implementation

def day_of_the_week(day, month, year):
    day_list = ["Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"]

    # Adjust month and year for Jan/Feb
    if month < 3:
        month += 12
        year -= 1

    year_of_century = year % 100
    century = year // 100

    # Zeller's Congruence formula
    # This formula is the core logic for calculating the day
    day_index = (day + (13 * (month + 1)) // 5 + year_of_century + (year_of_century // 4) + (century // 4) - (2 * century)) % 7

    # Python's modulo can return negative numbers, so adjust.
    day_index = (day_index + 7) % 7

    # Return the day of the week
    return day_list[day_index]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Invalid date components (e.g., month 0, day 0, year -1)	Handle invalid date components by either returning an error message or defaulting to a sensible default date (e.g., January 1, 1900) and documenting the behavior.
Dates outside the range supported by the algorithm (e.g., before the Gregorian calendar was adopted)	Check if the input date is within the supported range and return an error or a predefined result if outside.
Leap years and their impact on the day of the week calculation, especially around February 29th	Ensure the algorithm correctly accounts for leap years by incorporating leap year logic in the date calculations.
Dates close to integer limits (potential overflow during calculations)	Use appropriate data types (e.g., long) and modular arithmetic to prevent integer overflow during calculations.
Ambiguous date formats (e.g., mm/dd/yyyy vs dd/mm/yyyy)	Specify the expected date format and validate the input accordingly, returning an error if the format is incorrect.
Epoch year is a leap year (Year 0000 being invalid)	Do not assume year 0 to be a valid leap year, and use the correct offset to calculate the Julian day.
Gregorian calendar reform date	If the algorithm spans dates before and after the Gregorian reform, incorporate logic to handle the change in calendar systems.
Very large year values that could introduce precision errors or performance issues	Ensure that the algorithm handles large year values gracefully without introducing precision errors or performance degradation.

Invalid date components (e.g., month 0, day 0, year -1)

How to Handle:

Handle invalid date components by either returning an error message or defaulting to a sensible default date (e.g., January 1, 1900) and documenting the behavior.

Dates outside the range supported by the algorithm (e.g., before the Gregorian calendar was adopted)

How to Handle:

Check if the input date is within the supported range and return an error or a predefined result if outside.

Leap years and their impact on the day of the week calculation, especially around February 29th

How to Handle:

Ensure the algorithm correctly accounts for leap years by incorporating leap year logic in the date calculations.

Dates close to integer limits (potential overflow during calculations)

How to Handle:

Use appropriate data types (e.g., long) and modular arithmetic to prevent integer overflow during calculations.

Ambiguous date formats (e.g., mm/dd/yyyy vs dd/mm/yyyy)

How to Handle:

Specify the expected date format and validate the input accordingly, returning an error if the format is incorrect.

Epoch year is a leap year (Year 0000 being invalid)

How to Handle:

Do not assume year 0 to be a valid leap year, and use the correct offset to calculate the Julian day.

Gregorian calendar reform date

How to Handle:

If the algorithm spans dates before and after the Gregorian reform, incorporate logic to handle the change in calendar systems.

Very large year values that could introduce precision errors or performance issues

How to Handle:

Ensure that the algorithm handles large year values gracefully without introducing precision errors or performance degradation.