notes.html

problem 19 · 62 lines

<article>
<h3>Problem Analysis</h3>
<p>
    This problem asks us to count how many times the first day of a month landed on a Sunday over a
    100-year window. The essential mathematical tool is
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Modular_arithmetic" rel="noopener noreferrer" target="_blank">modular arithmetic</a>
    applied to the day-of-week cycle. The days of the week form a cycle of length 7: if today is a
    Monday, then 365 days later is whatever day you get by computing 365 mod 7 = 1 step forward.
    Because the day of week is inherently cyclic with period 7, we never need to track absolute date
    counts - only their residues modulo 7. Given a single known anchor date (1 Jan 1900 was a
    Monday), we can compute the day of week for any future date by accumulating the number of
    intervening days and reducing modulo 7.
  </p>
<p>
    The only subtlety is the
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Leap_year#Gregorian_calendar" rel="noopener noreferrer" target="_blank">Gregorian leap-year rule</a>:
    a year is a leap year if divisible by 4, except for century years, which must additionally be
    divisible by 400. This rule decides whether February contributes 28 or 29 days and therefore how
    many days separate consecutive month boundaries. The problem is tractable because the search
    space is tiny: the 20th century spans only 1200 months. A simple linear scan over months
    suffices, giving complexity O(Y x 12) = O(Y) where Y is the number of years in the range - in
    practice an instantaneous constant-time computation. No combinatorics or
    <a class="reference-source" href="https://en.wikipedia.org/wiki/Dynamic_programming" rel="noopener noreferrer" target="_blank">dynamic programming</a>
    is required.
  </p>
<h3>Solution Approach</h3>
<h4>Day-of-week Simulation (C and Python)</h4>
<p>
    Both files implement the same conceptual algorithm - anchor to a known date and advance month by
    month - but the C version computes the day-of-week from first principles while the Python version
    delegates to the standard library.
  </p>
<p>
<strong>Step 1 - Establish a reference point.</strong> The problem states that 1 January 1900 was
    a Monday. In the C solution I encode Monday as 0, Tuesday as 1, ..., Sunday as 6. This zero-based
    scheme makes the modulo-7 arithmetic clean, since the residue is exactly the day index.
  </p>
<p>
<strong>Step 2 - Advance to the start year.</strong> The count begins in 1901, not 1900. Rather
    than hard-code the day of week for 1 January 1901, I advance the counter from the known anchor by
    adding 366 for each leap year and 365 otherwise, reducing modulo 7 at each step. This keeps the
    code general: it accepts any start year as input.
  </p>
<p>
<strong>Step 3 - Iterate over every first-of-month.</strong> For each year from
    <code>start_year</code> to <code>end_year</code>, and for each month 1 through 12, I first check
    whether the current day-of-week is 6 (Sunday) and increment the count if so, then advance the
    counter by the number of days in that month. The <code>days_in_month</code> helper encodes the
    standard month-length table and applies the <a class="reference-source" href="https://en.wikipedia.org/wiki/Leap_year#Gregorian_calendar" rel="noopener noreferrer" target="_blank">leap-year</a> correction to February. Crucially, I check
    before advancing, so <code>dow</code> always represents "the day of week on the 1st of the
    current month."
  </p>
<p>
<strong>Language differences.</strong> The C solution does everything manually with loops and a
    static array. The Python solution lets <code>datetime.date(y, m, 1).isoweekday()</code> do the
    work - it returns 7 for Sunday, so Python never tracks the day-of-week or the <a class="reference-source" href="https://en.wikipedia.org/wiki/Leap_year#Gregorian_calendar" rel="noopener noreferrer" target="_blank">leap-year</a> rule
    itself. This is more concise and less error-prone, at the cost of a function call per date, which
    is negligible at this scale. The Python solution sums a <a class="reference-source" href="https://docs.python.org/3/reference/expressions.html#generator-expressions" rel="noopener noreferrer" target="_blank">generator expression</a>, idiomatically
    counting matches without building an intermediate list.
  </p>
</article>