# Day of the Week
**Difficulty:** EASY
[External](https://leetcode.com/problems/day-of-the-week)
Canonical: https://scaleengineer.com/dsa/problems/day-of-the-week
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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`.

# Approaches
## Counting Days from a Reference Date
This approach involves selecting a known date and its corresponding day of the week as a reference point. We then calculate the total number of days that have passed between this reference date and the target date. The day of the week for the target date can be determined by taking this total number of days, adding the reference day's index, and finding the result modulo 7.
**Time:** O(Y + M), where Y is the number of years between the given year and the reference year (1971), and M is the number of months. Given the constraints (1971-2100), the number of iterations is small and bounded, so it can be considered O(1). However, compared to other approaches, it's less efficient as it involves loops. · **Space:** O(1), as we only use a few variables and constant-size arrays to store data.
**Pros:** Intuitive and easy to understand the logic.; Doesn't rely on complex mathematical formulas.; Demonstrates handling of dates and leap years from first principles.
**Cons:** More code to write compared to other methods.; Prone to off-by-one errors in counting days or handling the reference date.; Less efficient than a direct formula if the year range were large.
### Explanation
We'll use January 1st, 1971, as our reference date. A quick search reveals this day was a Friday.
We can represent the days of the week with numbers, for example, Sunday=0, Monday=1, ..., Friday=5, Saturday=6.
The algorithm proceeds as follows:
1.  Calculate the total number of days from the reference year (1971) up to the year just before the input `year`. This involves iterating through each year and adding 365 days for a common year and 366 for a leap year.
2.  Calculate the total number of days in the months preceding the input `month` within the input `year`. We'll use a pre-filled array for the number of days in each month, and we must remember to adjust for February in a leap year.
3.  Add the input `day` to the total count.
4.  Since our reference is Jan 1st, 1971, we have counted the days from Jan 1st, 1971, to the given date. The total number of days elapsed is `total days - 1`.
5.  The final day of the week is `(total elapsed days + reference day index) % 7`. Since Jan 1, 1971 was a Friday (index 5), the formula is `(total_days_from_1971_start + 5 - 1) % 7` which simplifies to `(totalDays + 4) % 7`.
A year is a leap year if it is divisible by 4, except for years divisible by 100 but not by 400. The rule is: `(year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)`.

```java
class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        String[] daysOfWeek = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        int[] daysInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

        // Reference date: Jan 1, 1971 was a Friday.
        int totalDays = 0;

        // 1. Count days for full years passed since 1971
        for (int y = 1971; y < year; y++) {
            totalDays += isLeapYear(y) ? 366 : 365;
        }

        // 2. Count days for full months passed in the current year
        for (int m = 1; m < month; m++) {
            if (m == 2 && isLeapYear(year)) {
                totalDays += 29;
            } else {
                totalDays += daysInMonth[m];
            }
        }

        // 3. Count days in the current month
        totalDays += day;

        // Jan 1, 1971 was a Friday. Our daysOfWeek array starts with Sunday.
        // The index of Friday is 5.
        // The number of days passed since Jan 1, 1971 is `totalDays - 1`.
        // The index of the day is ( (days passed) + (index of ref day) ) % 7
        // index = ( (totalDays - 1) + 5 ) % 7 = (totalDays + 4) % 7
        return daysOfWeek[(totalDays + 4) % 7];
    }

    private boolean isLeapYear(int year) {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }
}
```
### Algorithm
- 1. Define an array for the days of the week and an array for the number of days in each month.
- 2. Initialize a counter `totalDays` to 0.
- 3. Iterate from the reference year (1971) to `year - 1`. In each iteration, add 365 or 366 to `totalDays` based on whether the year is a leap year.
- 4. Iterate from month 1 to `month - 1`. In each iteration, add the number of days in that month to `totalDays`. Account for leap years for February.
- 5. Add the given `day` to `totalDays`.
- 6. Calculate the final day index using the total days and the reference day (Friday for Jan 1, 1971). The formula is `(totalDays + 4) % 7`.
- 7. Return the day of the week from the array using the calculated index.

## Using Built-in Date/Time Library
Modern programming languages provide robust libraries for handling dates and times. In Java, we can use the `java.time.LocalDate` class (introduced in Java 8) or the older `java.util.Calendar` class. This approach leverages the built-in functionality to parse the date and directly query the day of the week.
**Time:** O(1). The underlying implementation is highly optimized and performs the calculation in constant time for any valid date. · **Space:** O(1). A few objects are created, but the space usage does not depend on the input values.
**Pros:** Extremely simple and concise code.; Highly reliable and less error-prone, as it relies on a well-tested standard library.; Handles all date-related complexities (like leap years, calendar changes) transparently.
**Cons:** May not be permitted in an interview setting that aims to test fundamental algorithm design.; It abstracts away the core logic of how the day of the week is actually calculated.
### Explanation
The `java.time` package is the modern and recommended way to handle dates in Java.
We can create a `LocalDate` object representing the given date using the `LocalDate.of(year, month, day)` factory method.
Once we have the `LocalDate` object, we can call the `getDayOfWeek()` method. This method returns a `DayOfWeek` enum value (e.g., `DayOfWeek.SATURDAY`).
The final step is to convert this enum value into the required string format. The `DayOfWeek` enum values are in all caps (e.g., "SATURDAY"). We need to convert this to title case (e.g., "Saturday").

```java
import java.time.LocalDate;
import java.time.format.TextStyle;
import java.util.Locale;

class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        // Create a LocalDate object from the given year, month, and day
        LocalDate date = LocalDate.of(year, month, day);
        
        // Get the DayOfWeek enum
        java.time.DayOfWeek dayOfWeekEnum = date.getDayOfWeek();
        
        // Format the enum name to the required title case string
        // e.g., MONDAY -> Monday
        return dayOfWeekEnum.getDisplayName(TextStyle.FULL, Locale.ENGLISH);
    }
}
```
### Algorithm
- 1. Import the necessary `java.time.LocalDate` class.
- 2. Create an instance of `LocalDate` by calling `LocalDate.of(year, month, day)`.
- 3. Call the `getDayOfWeek()` method on the `LocalDate` instance to get the `DayOfWeek` enum.
- 4. Use `getDisplayName(TextStyle.FULL, Locale.ENGLISH)` to get the full name of the day in English (e.g., "Saturday").
- 5. Return the resulting string.

## Mathematical Formula (Sakamoto's Algorithm)
This approach uses a direct mathematical formula to compute the day of the week without any iteration. Several such formulas exist, like Zeller's Congruence. A particularly elegant and simple one is Sakamoto's algorithm. It involves a few arithmetic operations and a small lookup table for month offsets.
**Time:** O(1). The calculation involves a fixed number of arithmetic operations, regardless of the input date. This is the most computationally efficient approach. · **Space:** O(1). We use a constant-size array for the month offsets and another for the day names.
**Pros:** The fastest possible runtime performance.; Elegant and purely mathematical.; Demonstrates deep knowledge of calendar algorithms.
**Cons:** The formula is non-obvious and difficult to derive or remember from scratch. It can seem like "magic".; Less readable than the counting approach for someone unfamiliar with the algorithm.
### Explanation
Sakamoto's algorithm calculates the day of the week (where Sunday = 0, Monday = 1, etc.) for any Gregorian date.
The formula is: `dayOfWeek = (year + year/4 - year/100 + year/400 + t[month-1] + day) % 7`
The components are:
- `year`, `month`, `day`: The input date.
- `t`: A lookup table for the number of days passed in the year before the given month begins. The table is `t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}`.
- An important adjustment: if the month is January or February (`month < 3`), we treat it as part of the previous year. So, we decrement `year` by 1. This is because the leap day (Feb 29) affects the calculation for all subsequent days in that year.
The terms `year/4 - year/100 + year/400` account for the number of leap years that have occurred since year 0.
The final result of the formula is an integer from 0 to 6, which can be mapped to the corresponding day of the week string.

```java
class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        String[] daysOfWeek = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        
        // Sakamoto's algorithm
        int[] t = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
        
        if (month < 3) {
            year -= 1;
        }
        
        int dayIndex = (year + year / 4 - year / 100 + year / 400 + t[month - 1] + day) % 7;
        
        return daysOfWeek[dayIndex];
    }
}
```
### Algorithm
- 1. Define an array for the days of the week strings, ordered from Sunday to Saturday.
- 2. Define the month offset table `t`.
- 3. Check if the month is January or February. If so, decrement the year by 1.
- 4. Apply Sakamoto's formula to calculate the day index.
- 5. Use the calculated index to retrieve the day name from the `daysOfWeek` array.
- 6. Return the day name.

# Solutions
### Java

```java
import java.util.Calendar ; class Solution { private static final String [] WEEK = { "Sunday" , "Monday" , "Tuesday" , "Wednesday" , "Thursday" , "Friday" , "Saturday" }; public static String dayOfTheWeek ( int day , int month , int year ) { Calendar calendar = Calendar . getInstance (); calendar . set ( year , month - 1 , day ); return WEEK [ calendar . get ( Calendar . DAY_OF_WEEK ) - 1 ]; } }
```

### CPP

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

```

### Python

```python
class Solution:
    def dayOfTheWeek(self, day: int, month: int,
                     year: int) -> str: return datetime . date(year, month, day). strftime('%A')

```