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.

Day of the Week Algorithm

We can easily know that the 1/Jan/1970 is Thursday. And 1 of January, 1970 is the famous date in Computer Science, because the Unix Time is the number of seconds elapsed from Unix epoch which is 00:00:00 UTC on 1 January 1970.

We just need to compute the number of days since Unix epoch. In order to do this, we need a leap year function – which will tell us the number of days in a year (either 365 or 366 if leap year), and also 28 or 29 (leap) days in February.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        string names[7] { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        int total = 0;
        for (int i = 1970; i < year; ++ i) {
            if (isLeap(i)) {
                total += 366;
            } else {
                total += 365;
            }
        }
        for (int i = 1; i < month; ++ i) {
            switch (i) {
                case 1: total += 31; break;
                case 2: total += (isLeap(year) ? 29 : 28); break;
                case 3: total += 31; break;
                case 4: total += 30; break;
                case 5: total += 31; break;
                case 6: total += 30; break;
                case 7: total += 31; break;
                case 8: total += 31; break;
                case 9: total += 30; break;
                case 10: total += 31; break;
                case 11: total += 30; break;
            }
        }
        return names[(4 + total + day - 1) % 7];
    }
private:
    bool isLeap(int year) {
        if (year % 400 == 0) return true;
        if (year % 100 == 0) return false;
        if (year % 4 == 0) return true;
        return false;
    }    
};

class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        string names[7] { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        int total = 0;
        for (int i = 1970; i < year; ++ i) {
            if (isLeap(i)) {
                total += 366;
            } else {
                total += 365;
            }
        }
        for (int i = 1; i < month; ++ i) {
            switch (i) {
                case 1: total += 31; break;
                case 2: total += (isLeap(year) ? 29 : 28); break;
                case 3: total += 31; break;
                case 4: total += 30; break;
                case 5: total += 31; break;
                case 6: total += 30; break;
                case 7: total += 31; break;
                case 8: total += 31; break;
                case 9: total += 30; break;
                case 10: total += 31; break;
                case 11: total += 30; break;
            }
        }
        return names[(4 + total + day - 1) % 7];
    }
private:
    bool isLeap(int year) {
        if (year % 400 == 0) return true;
        if (year % 100 == 0) return false;
        if (year % 4 == 0) return true;
        return false;
    }    
};

Once we have the number of days since 1/1/1970, we can deduce which day of the week it is easily (based on the modulo operator). You can however pick 1/1/1971 which is Friday as well since the input year is from 1971 to 2100. The time and space complexity is both O(1) constant (known year range – trivial computational efforts).

Calendar

–EOF (The Ultimate Computing & Technology Blog) —