1154. Day of the Year
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 49.1%
Problem Breakdown
The problem requires determining the day number of the year for a given date in the Gregorian calendar. The input is a string formatted as YYYY-MM-DD, representing a valid date between January 1, 1900, and December 31, 2019. The output should be an integer representing the day number within that year.
Inputs:
- A string
datein the formatYYYY-MM-DD.
Outputs:
- An integer representing the day number of the year.
Implicit Constraints or Edge Cases:
- Leap years need to be considered, where February has 29 days.
- The input is always a valid date within the specified range.
- The input format is strictly followed with hyphens at specific positions.
Intuition
A brute-force approach would involve iterating through each day from January 1st of the given year up to the given date, counting the days. However, this approach is inefficient as it requires iterating through potentially hundreds of days.
The key insight is to use a precomputed list of cumulative days for each month in a non-leap year and adjust for leap years when necessary. This allows us to directly calculate the day number by summing up the days from previous months and adding the day of the current month.
Approach
-
Precompute Days in Each Month:
- Create an array
days_in_monthwhere each index represents a month (0 for January, 1 for February, etc.) and the value at that index is the number of days in that month for a non-leap year.
- Create an array
-
Leap Year Check:
- Implement a helper function to determine if a given year is a leap year. A year is a leap year if it is divisible by 4 but not every year divisible by 100, unless it is also divisible by 400.
-
Extract Date Components:
- Parse the input string
dateto extract the year, month, and day as integers.
- Parse the input string
-
Calculate Day Number:
- Use the precomputed array to get the cumulative days for the months before the given month.
- Add the day of the current month to this cumulative sum.
- If it’s a leap year and the month is after February, add an extra day.
Complexity Analysis
- Time Complexity: O(1) because the operations involve fixed-size arrays and simple arithmetic.
- Space Complexity: O(1) as we only use a fixed amount of additional space for the
days_in_montharray and a few variables.
Solution
def dayOfYear(date: str) -> int:
# Precompute days in each month for a non-leap year
days_in_month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
# Helper function to check if a year is a leap year
def is_leap_year(year: int) -> bool:
return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)
# Extract year, month, and day from the date string
year, month, day = map(int, date.split('-'))
# Calculate the cumulative days for months before the given month
day_of_year = sum(days_in_month[:month])
# Add the day of the current month
day_of_year += day
# If it's a leap year and after February, add an extra day
if is_leap_year(year) and month > 2:
day_of_year += 1
return day_of_year
# Example usage:
print(dayOfYear("2019-01-09")) # Output: 9
print(dayOfYear("2019-02-10")) # Output: 41
print(dayOfYear("2003-03-01")) # Output: 60
print(dayOfYear("2004-03-01")) # Output: 61
Edge Cases Handled
- Leap Year Calculation: The code correctly identifies leap years and adjusts the day count for February accordingly.
- Month Boundaries: The cumulative days calculation ensures that the correct number of days are added based on the month.
- Year Range: The problem constraints ensure that the input year is within a valid range, so no special handling for out-of-range years is necessary.