algoadvance

Leetcode 1185. Day of the Week

Problem Statement

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 strings: "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday".

Clarifying Questions

  1. Range of Dates: Are the provided dates guaranteed to be valid?
    • Yes, you can assume the dates are valid and lie within the Gregorian calendar.
  2. Leap Years: Should the implementation consider leap years?
    • Yes, the implementation should properly account for leap years when calculating the day.
  3. Date Range: Is there any specific range for the year?
    • You can assume years will be within the typical range for Gregorian calendar dates (e.g., 1900 to 2100).

Strategy

  1. Zeller’s Congruence: One common way to find the day of the week for any given date is using Zeller’s Congruence. This algorithm is efficient and perfectly suited for this problem.

  2. Handling Month and Year Corrections: According to Zeller’s Congruence:
    • For months January and February, we treat them as month 13 and 14 of the previous year.
  3. Formula:
    • Given d as day, m as month, and y as year: ( h = (d + \left\lfloor \frac{{13(m + 1)}}{5} \right\rfloor + K + \left\lfloor \frac{K}{4} \right\rfloor + \left\lfloor \frac{J}{4} \right\rfloor + 5J) \mod 7 )
    • Where:
      • K = y % 100 (year of the century)
      • J = y // 100 (zero-based century)
    • h will be the weekday (0 for Saturday, 1 for Sunday, …, 6 for Friday).

Code

Here is the C++ code to implement this strategy:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        vector<string> days = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        
        if (month < 3) {
            month += 12;
            year--;
        }
        
        int K = year % 100;
        int J = year / 100;
        
        int h = day + 13 * (month + 1) / 5 + K + K / 4 + J / 4 + 5 * J;
        h = h % 7;
        
        // Note: In Zeller's algorithm, 0 corresponds to Saturday
        // Using the array, 0 should correspond to Sunday
        h = (h + 5) % 7;
        
        return days[h];
    }
};

int main() {
    Solution sol;
    // Example usage:
    cout << sol.dayOfTheWeek(31, 8, 2019) << endl; // Output: "Saturday"
    cout << sol.dayOfTheWeek(18, 7, 1999) << endl; // Output: "Sunday"
    cout << sol.dayOfTheWeek(15, 8, 1993) << endl; // Output: "Sunday"
    return 0;
}

Time Complexity

The time complexity of this solution is O(1), as the calculation involves only a fixed number of arithmetic operations irrespective of the size of the input.

The space complexity is also O(1), as no extra space is used that scales with the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI