Labels

Project Euler #19: Counting Sundays (C++)

Question
You are given the following information, but you may prefer to do some research for yourself.
  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Answer : 171

Hacker Rank Problem

Solution


 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>

const unsigned int Sunday = 1;

unsigned int getWeekday(unsigned long long year, unsigned int month, unsigned int day)
{

  if (month <= 2)
  {
    month += 12;
    year--;
  }

  return (day +
          13 * (month + 1) / 5 +
          year + year / 4 - year / 100 + year / 400)
         % 7;
}

int main()
{
  unsigned int tests;
  std::cin >> tests;
  while (tests--)
  {
    unsigned long long y1, y2;
    unsigned int m1, m2, d1, d2;
    std::cin >> y1 >> m1 >> d1;
    std::cin >> y2 >> m2 >> d2;

    if (y2 < y1 || (y2 == y1 && m2 < m1))
    {
      std::swap(y1,  y2);
      std::swap(m1, m2);
    }

    unsigned long long currentYear  = y1;
    unsigned int       currentMonth = m1;
    if (d1 > 1)
    {
      currentMonth++;

      if (currentMonth > 12)
      {
        currentMonth -= 12;
        currentYear++;
      }
    }

    unsigned int sum = 0;

    while (currentYear + 2800 < y2)
    {
      currentYear += 2800;
      sum += 4816;
    }
    
    while (currentMonth < m2 || currentYear < y2)
    {
      if (getWeekday(currentYear, currentMonth, 1) == Sunday)
        sum++;

      currentMonth++;

      if (currentMonth > 12)
      {
        currentMonth -= 12;
        currentYear++;
      }
    }
    if (getWeekday(currentYear, currentMonth, 1) == Sunday)
      sum++;

    std::cout << sum << std::endl;
  }
  return 0;
}
Labels:

Comments

Post a Comment

Popular Posts