CF 102697071 - Days between two Dates

CF 102697071 - Days between two Dates

Rating: -
Tags: -
Solve time: 2m 16s
Verified: yes

Solution

Problem Understanding

The task is to calculate how many calendar days separate two valid dates. Each date is written as a month name, a day number, and a year, for example June 21, 2019. The second date is guaranteed to be later than the first, so the answer is simply the forward distance from the first date to the second. Unlike the earlier version of this problem, leap years must be counted.

The input contains exactly two lines, one date per line. The output is one integer, representing the number of midnight-to-midnight day boundaries between those dates. For example, moving from June 21, 2019 to June 21, 2020 crosses 366 days because the interval contains February 29, 2020.

The statement does not publish a numerical bound on the years. The time limit is 1 second and the memory limit is 256 MB. Since the input consists of only two dates, the cleanest solution should use a constant amount of work rather than relying on the number of years between them. A solution that advances one day at a time performs one iteration per calendar day, so its running time grows with the distance between the dates. A solution based on an absolute day number avoids that dependency entirely.

There are several places where a seemingly simple implementation can be wrong. The first is the endpoints. For

June 21, 2019
June 22, 2019

the answer is 1, not 2. We are measuring elapsed days, so the starting date contributes zero days and the next date is exactly one day away. An implementation that counts both endpoints would produce an off-by-one answer.

The second issue is February in a leap year. For

February 28, 2020
March 1, 2020

the answer is 2, because February 29 lies between the two dates. A solution that treats every February as having 28 days would return 1.

The third issue is the complete Gregorian leap-year rule. A year divisible by 4 is usually a leap year, but a century year is not a leap year unless it is also divisible by 400. Thus

February 28, 1900
March 1, 1900

has answer 1, while

February 28, 2000
March 1, 2000

has answer 2. Checking only year % 4 == 0 incorrectly treats 1900 as a leap year.

The fourth issue is crossing a year boundary. For

December 31, 2019
January 1, 2020

the answer is 1. A calculation that only compares the day and month fields cannot handle this correctly because the year changes even though the dates are consecutive.

Approaches

The most direct solution is to start at the first date and repeatedly advance one day until reaching the second date. Each advance increments the answer by one. Advancing a date requires knowing how many days are in its current month, handling the transition to the next month, and handling the transition from December to January. February additionally depends on whether the current year is a leap year. This method is correct because every iteration corresponds to exactly one calendar day in the interval.

The problem with that approach is its dependence on the distance between the dates. If the years differ by (Y), the loop performs roughly (365Y) iterations. For example, a gap of one million years would require about 365 million day transitions. Even though each transition is simple, that is far beyond what we want from a 1 second solution. Since the statement does not give a small upper bound on the year difference, a day-by-day simulation is not a robust choice.

The key observation is that a date can be converted into an absolute day index. Once both dates have such an index, their distance is simply the difference between the two indices. We do not need to simulate any of the individual days.

To construct this index, count all complete years before the date, then all complete months before the date inside its year, and finally add the day number. A complete ordinary year contributes 365 days. A complete leap year contributes 366. The number of leap years before year (y) can be calculated directly using

\left\lfloor\frac{y-1}{100}\right\rfloor + \left\lfloor\frac{y-1}{400}\right\rfloor. ]

The subtraction for 100 removes century years that are not leap years, while the addition for 400 restores years such as 2000.

We can then define a function that maps every valid date to the number of days before it relative to an arbitrary fixed origin. The choice of origin does not matter, because it cancels when we subtract the two dates. This reduces the entire problem to a fixed number of arithmetic operations.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	(O(D)), where (D) is the number of days between the dates	(O(1))	Too slow for large date gaps
Optimal	(O(1))	(O(1))	Accepted

Algorithm Walkthrough

1. Read the two date strings and split each one into its month name, day, and year. The comma after the day is part of the input formatting, so remove it before converting the day to an integer.
2. Convert the month name to a number from 1 through 12. A fixed dictionary is sufficient because there are only twelve possible month names.
3. Define the Gregorian leap-year predicate. A year is a leap year if it is divisible by 400, or if it is divisible by 4 but not by 100.
4. Define a function days_before_year(year) that returns the number of days in all years strictly before the given year. There are year - 1 preceding years, and the number of leap years among them is given by the formula above. Thus the total is 365 * (year - 1) + leap_years.
5. Define a function days_before_date(year, month, day). Start with the days before the year, then add the lengths of all months before the current month, and finally add day - 1. We use day - 1 because the first day of a month should add zero elapsed days from the beginning of that month.
6. Compute the absolute day index for both input dates and subtract the first index from the second. The statement guarantees that the second date is later, so the result is already non-negative.

The key invariant is that days_before_date(y, m, d) represents exactly the number of complete calendar days preceding the beginning of date (y, m, d). Every complete year contributes its correct 365 or 366 days, every complete month contributes its actual length, and day - 1 counts the completed days in the current month. Consequently, subtracting the two indices removes everything before the first date and leaves exactly the days separating the two dates.

Python Solution

import sys
input = sys.stdin.readline

MONTHS = {
    "January": 1,
    "February": 2,
    "March": 3,
    "April": 4,
    "May": 5,
    "June": 6,
    "July": 7,
    "August": 8,
    "September": 9,
    "October": 10,
    "November": 11,
    "December": 12,
}

MONTH_DAYS = [
    31, 28, 31, 30, 31, 30,
    31, 31, 30, 31, 30, 31
]

def is_leap(year):
    return year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)

def parse_date(s):
    parts = s.strip().replace(",", "").split()
    month = MONTHS[parts[0]]
    day = int(parts[1])
    year = int(parts[2])
    return year, month, day

def days_before_year(year):
    y = year - 1
    leap_years = y // 4 - y // 100 + y // 400
    return 365 * y + leap_years

def days_before_date(year, month, day):
    result = days_before_year(year)

    for m in range(1, month):
        result += MONTH_DAYS[m - 1]

    if month > 2 and is_leap(year):
        result += 1

    result += day - 1
    return result

def solve():
    date1 = parse_date(input())
    date2 = parse_date(input())

    first = days_before_date(*date1)
    second = days_before_date(*date2)

    print(second - first)

if __name__ == "__main__":
    solve()

The MONTHS dictionary handles the textual month representation directly instead of using fragile string comparisons. After removing the comma, an input such as June 21, 2019 becomes three clean tokens: June, 21, and 2019.

The is_leap function uses the complete Gregorian rule. Writing the condition as year % 400 == 0 or (year % 4 == 0 and year % 100 != 0) handles ordinary leap years, non-leap century years, and leap century years in one expression.

The days_before_year function uses year - 1 rather than year. This boundary is easy to get wrong. For year 2020, we need the number of leap years from years 1 through 2019, so every division is performed on 2019.

The month loop adds only months strictly before the current month. For a date in January, the loop executes zero times. For a date in March, it adds January and February. February's extra day is added separately because it depends on the current year.

The final addition is day - 1. For January 1, the function must count zero days inside January, not one. This choice is what makes consecutive dates differ by exactly one.

Python integers do not overflow, so even very large year values do not require special integer handling.

Worked Examples

Sample 1

The provided sample is:

June 21, 2019
June 21, 2020

The following trace shows the important quantities rather than expanding every month calculation.

Date	Year contribution	Month contribution	Day contribution	Absolute day index
June 21, 2019	days before 2019	Jan through May	20	index 1
June 21, 2020	days before 2020	Jan through May	20	index 2

The difference between the two year contributions is 366 because 2020 itself is not yet included in the second date's completed years, while 2019 is a leap-free year. The interval from June 21, 2019 to June 21, 2020 nevertheless contains February 29, 2020, because that leap day occurs before the second date. The final difference is 366.

Sample 2

Consider the leap-day boundary:

February 28, 2020
March 1, 2020

Date	Complete months	Leap adjustment	Day contribution	Absolute day index
February 28, 2020	January = 31	0	27	A
March 1, 2020	January + February = 59	+1	0	B

The February 28 date has 27 completed days inside February. March 1 has all 59 ordinary days from January and February before it, plus one additional day because 2020 is a leap year. The difference is 2, representing February 29 as the day between the two supplied dates.

Complexity Analysis

Measure	Complexity	Explanation
Time	(O(1))	There are only 12 possible months, so the month loop has a fixed maximum of 11 iterations.
Space	(O(1))	The solution stores only the parsed dates and a constant-size month dictionary.

The constant-time approach does not depend on the number of years separating the dates. Even if the input dates are extremely far apart, the program performs the same bounded amount of arithmetic and at most eleven month additions per date. It therefore fits comfortably within the 1 second and 256 MB limits stated by the problem.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

MONTHS = {
    "January": 1,
    "February": 2,
    "March": 3,
    "April": 4,
    "May": 5,
    "June": 6,
    "July": 7,
    "August": 8,
    "September": 9,
    "October": 10,
    "November": 11,
    "December": 12,
}

MONTH_DAYS = [
    31, 28, 31, 30, 31, 30,
    31, 31, 30, 31, 30, 31
]

def is_leap(year):
    return year % 400 == 0 or (year % 4 == 0 and year % 100 != 0)

def parse_date(s):
    parts = s.strip().replace(",", "").split()
    return int(parts[2]), MONTHS[parts[0]], int(parts[1])

def days_before_year(year):
    y = year - 1
    return 365 * y + y // 4 - y // 100 + y // 400

def days_before_date(year, month, day):
    result = days_before_year(year)

    for m in range(1, month):
        result += MONTH_DAYS[m - 1]

    if month > 2 and is_leap(year):
        result += 1

    return result + day - 1

def solution(inp):
    lines = inp.strip().splitlines()
    d1 = parse_date(lines[0])
    d2 = parse_date(lines[1])

    return str(
        days_before_date(*d2) - days_before_date(*d1)
    ) + "\n"

def run(inp: str) -> str:
    return solution(inp)

# provided sample
assert run(
    "June 21, 2019\n"
    "June 21, 2020\n"
) == "366\n", "sample 1"

# minimum-size interval
assert run(
    "January 1, 2000\n"
    "January 2, 2000\n"
) == "1\n", "consecutive dates"

# same date
assert run(
    "May 17, 2024\n"
    "May 17, 2024\n"
) == "0\n", "same date"

# leap-day boundary
assert run(
    "February 28, 2020\n"
    "March 1, 2020\n"
) == "2\n", "leap day"

# century that is not a leap year
assert run(
    "February 28, 1900\n"
    "March 1, 1900\n"
) == "1\n", "1900 is not a leap year"

# century that is a leap year
assert run(
    "February 28, 2000\n"
    "March 1, 2000\n"
) == "2\n", "2000 is a leap year"

# year boundary
assert run(
    "December 31, 2019\n"
    "January 1, 2020\n"
) == "1\n", "year boundary"

Test input	Expected output	What it validates
January 1, 2000 to January 2, 2000	1	Minimum non-zero interval and day - 1 handling
May 17, 2024 to May 17, 2024	0	Equal dates
February 28, 2020 to March 1, 2020	2	Leap-day boundary
February 28, 1900 to March 1, 1900	1	Century year that is not leap
February 28, 2000 to March 1, 2000	2	Century year divisible by 400
December 31, 2019 to January 1, 2020	1	Year transition and endpoint counting

Edge Cases

The consecutive-date case

January 1, 2000
January 2, 2000

maps the first date to a day index ending in day - 1 = 0 and the second to one greater. Their difference is 1. The algorithm never counts the starting date as an elapsed day.

The equal-date case

May 17, 2024
May 17, 2024

produces identical absolute indices, so their difference is 0. Although the statement says the second date is after the first, accepting equality costs nothing and makes the date conversion function behave naturally.

For the leap-day boundary

February 28, 2020
March 1, 2020

February contributes 28 days to the prefix before March in an ordinary year and 29 in 2020. The leap adjustment is applied only when month > 2, so it affects March and later dates but does not incorrectly shift February 28 itself. The result is 2.

For the century boundary

February 28, 1900
March 1, 1900

the expression 1900 % 100 == 0 makes 1900 non-leap because it is not divisible by 400. The prefix before March therefore contains 59 days from January and February, giving a difference of 1.

For the corresponding special case

February 28, 2000
March 1, 2000

2000 is divisible by 400, so it is a leap year. March begins one day later than it would in a normal year, and the answer becomes 2.

Finally, for

December 31, 2019
January 1, 2020

the first date has all months before December included in its year prefix, while the second date starts a new year's month calculation. The difference between their absolute indices is exactly 1, showing that year transitions require no special case in the final subtraction. The date-to-index representation handles them automatically.