1185. Day of the Week


Problem Description

This problem requires determining the day of the week for a specific date provided by the user. The input is given as three separate integers that denote the day (day), the month (month), and the year (year). The expected output is a string that represents the name of the corresponding day of the week, which can be any of these: "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", or "Saturday".

Understanding how to map a specific date to a day of the week involves knowledge of calendars and possibly some algorithmic computation. Modern programming languages include date and time libraries that can make this task straightforward, but the intellectual challenge lies in calculating it manually, using a known algorithm like Zeller's Congruence.

Intuition

The intuition behind the solution is based on the understanding that dates follow a regular pattern which repeats every week. However, manual calculation of the day for a given date from scratch is complex and involves taking into account leap years, the varying number of days in each month, and adjustments for the Gregorian calendar corrections.

One direct approach is to leverage the built-in capabilities of the datetime library in Python that abstracts these complexities and provides a simple method to get the day of the week. The datetime.date(year, month, day).strftime('%A') function constructs a date object with the given year, month, and day, and then formats it as a string representing the full name of the day of the week ('%A').

Additionally, the reference provided suggests using the Zeller formula as an alternative approach, which is a mathematical algorithm that can output the day of the week for any given date in the Gregorian calendar. This approach is an example of how such a problem could be solved before widespread use of computers and can be fun to implement and understand.

However, in a practical application where the algorithm's performance and simplicity are more critical, it is advisable to use built-in language features like datetime for reliability and efficiency, unless the problem specifically restricts their use.

Solution Approach

In the provided Python solution, the datetime library is utilized, which is a built-in Python module designed to work with date and time. This library takes care of the complex computations internally and provides a straightforward interface for getting the day of the week for a given date.

Implementation Steps:

  1. The datetime.date(year, month, day) function constructs a date object from the provided day, month, and year.
  2. The .strftime('%A') method is called on the date object to format it into a human-readable string that represents the full name of the day of the week. The '%A' format code tells strftime to extract the full weekday name.

Since the reference solution approach also hints at Zeller's formula, let's explore that method briefly:

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 involves a formularization that takes into account the day, month, year, and some constants representing the days ("Saturday" = 0, "Sunday" = 1, "Monday" = 2, etc.).

The formula looks like this:

1h = (q + ((13*(m + 1)) / 5) + K + (K / 4) + (J / 4) - 2 * J) % 7
2
3Where:
4
5h = day of the week (0 = Saturday, 1 = Sunday, 2 = Monday, ...)
6q = day of the month
7m = month (3 = March, 4 = April, 5 = May, ..., 14 = February)
8K = year of the century (year % 100)
9J = zero-based century (year / 100)

It's important to note that the original month numberings must be adjusted such that March is 3 and February is 14, which means January and February are considered as the 13th and 14th months of the previous year.

While Zeller's Congruence is an elegant solution, the Python datetime method provides a cleaner and less error-prone implementation for everyday programming needs.

It's evident that the datetime method is more straightforward and does not explicitly involve understanding the internal calculations of day-to-week mappings. This simplicity is why the Python datetime solution is often preferred for practical applications.

Example Walkthrough

Let's walk through an example to illustrate the solution approach using Python's datetime module. Consider that we want to find out the weekday for the date February 15, 2023. Here’s how the provided solution approach would be implemented step by step:

Step 1: Construct the Date Object

We start by creating a date object in Python for the given date — in this case, February 15, 2023. We use the datetime.date function, passing in the year 2023, the month 2, and the day 15.

1import datetime
2date_object = datetime.date(2023, 2, 15)

The date_object now holds this specific date and allows us to perform operations on it, such as formatting to day names.

Step 2: Format and Get the Weekday

Now that we have a date object, we want to find out what day of the week this date falls on. We use the .strftime('%A') method on date_object to format it as a string that represents the full name of the day of the week.

1weekday_name = date_object.strftime('%A')
2print(weekday_name)  # Output should be "Wednesday"

The output of printing weekday_name should be "Wednesday", since February 15, 2023, indeed fell on a Wednesday.

This example demonstrates the simplicity of using Python's datetime library to determine the day of the week for a given date with minimal code. It abstracts all the complex calculations and adjustments that might otherwise be necessary, such as handling leap years, the irregular number of days in months, and century leap adjustments.

In contrast to manual methods like Zeller's Congruence, which can be a more mathematical and intriguing exercise to implement, using Python's built-in datetime features provides a faster and more readable way to achieve the same result in everyday practical programming scenarios.

Python Solution

1import datetime  # Ensure datetime module is imported
2
3class Solution:
4    def day_of_the_week(self, day: int, month: int, year: int) -> str:
5        # This method takes a day, month, and year, and returns the name of the day of the week.
6
7        # Create a date object with the provided year, month, and day.
8        date_object = datetime.date(year, month, day)
9      
10        # Return the full weekday name (e.g., 'Monday', 'Tuesday', etc.) as a string.
11        return date_object.strftime('%A')
12

Java Solution

1import java.util.Calendar;
2
3public class Solution {
4
5    // Array containing the days of the week for easy reference.
6    private static final String[] DAYS_OF_WEEK = {
7        "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
8    };
9
10    /**
11     * Returns the day of the week for a particular date.
12     *
13     * @param day   The day of the month (1-based).
14     * @param month The month of the year (1-based, January is 1).
15     * @param year  The year (e.g., 2021).
16     * @return The name of the day of the week.
17     */
18    public static String dayOfTheWeek(int day, int month, int year) {
19        // Obtain an instance of Calendar.
20        Calendar calendar = Calendar.getInstance();
21      
22        // Set the calendar to the specified date.
23        // The month is zero-based in Calendar, hence the need to subtract 1.
24        calendar.set(year, month - 1, day);
25      
26        // Get the day of the week from the Calendar (1 = Sunday, 7 = Saturday)
27        // and adjust by subtracting 1 to align with the index of DAYS_OF_WEEK array.
28        int dayOfWeekIndex = calendar.get(Calendar.DAY_OF_WEEK) - 1;
29      
30        // Return the string representation of the day of the week.
31        return DAYS_OF_WEEK[dayOfWeekIndex];
32    }
33}
34

C++ Solution

1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to find the day of the week for a given date
7    string dayOfTheWeek(int day, int month, int year) {
8        // Zeller's congruence algorithm adjustments for January and February
9        if (month < 3) {
10            month += 12;
11            year -= 1;
12        }
13      
14        // Extracting the century and year of the century
15        int century = year / 100;
16        year %= 100;
17      
18        // Zeller's congruence formula to calculate the day of the week
19        int weekDay = (century / 4 - 2 * century + year + year / 4 + 13 * (month + 1) / 5 + day - 1) % 7;
20      
21        // Array of week days starting with Sunday
22        vector<string> weekDays = {
23            "Sunday", "Monday", "Tuesday", "Wednesday",
24            "Thursday", "Friday", "Saturday"
25        };
26      
27        // Adjusting for negative values and returning the result
28        return weekDays[(weekDay + 7) % 7];
29    }
30};
31

Typescript Solution

1// Define an array of week days starting with Sunday
2const weekDays: string[] = [
3    "Sunday", "Monday", "Tuesday", "Wednesday",
4    "Thursday", "Friday", "Saturday"
5];
6
7// Function to find the day of the week for a given date
8function dayOfTheWeek(day: number, month: number, year: number): string {
9  
10    // Zeller's congruence algorithm adjustments for January and February
11    if (month < 3) {
12        month += 12;
13        year -= 1;
14    }
15  
16    // Extracting the century and year of the century
17    const century: number = Math.floor(year / 100);
18    year = year % 100;
19  
20    // Zeller's congruence formula to calculate the day of the week
21    let weekDay: number = (century / 4 - 2 * century + year + Math.floor(year / 4) + 13 * (month + 1) / 5 + day - 1) % 7;
22  
23    // Adjusting for negative values and returning the result
24    weekDay = (weekDay + 7) % 7; 
25    return weekDays[weekDay];
26}
27
28// Usage example:
29// const day: string = dayOfTheWeek(15, 8, 2021);
30// console.log(day); // Outputs the day of the week for August 15, 2021
31

Time and Space Complexity

The time complexity of the provided code snippet is O(1). This is because it utilizes Python's built-in datetime module to find the day of the week for a given date. This operation does not depend on the size of the input and takes constant time.

The space complexity is also O(1). The function only creates a single date object and formats it, not using any additional space that scales with the input size.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫