Efficient algorithm for converting number of days to years (including leap years)

Question

The problem I am writing a class for holding dates in c++, and I found the following problem: I have a number of days `N` since a reference date (in my case that would be Jan 1, 0001 AD), including the leap days that passed since the reference day. How can I convert this number to a year `Y`, month `M` and day `D` efficiently? I would like to do this as efficiently as possible, so the best implementation would obviously have O(1) complexity. The next sections will explain some of the things I already learned. Leap years To determine if a year is leap or not, there are a few rules: - Years which are divisible by 4 are leap - Exception to rule 1: years that are divisible with 100 are not leap - Exception to rule 2: years that are divisible with 400 are leap This would translate in code like this: ``` bool IsLeapYear(int year) { // Corrected after Henrick's suggestion if (year % 400 == 0) return true; if ((year % 4 == 0) && (year % 100 != 0)) return true; return false; } ``` An efficient…

Accepted Answer

Here are a few pointers. Note: For this exercise I will assume that when `N=0` that `Y % 400 == 0`.

1: There are a fixed number of days in each 400 year period `(400 * 365) + 100 + 1 - 4`.

The `+100` is for the leap years, the `+1` is for the leap year every 400 years and the `-4` is for not having a leap year every 100 years.

So your first line of code will be:

```
GetDate(int N, int &Y, int &M, int &D) {
  const int DAYS_IN_400_YEARS = (400*365)+97;
  int year = (N / DAYS_IN_400_YEARS) * 400;
  N = N % DAYS_IN_400_YEARS;
```

2: You can make your life a great deal easier if you treat March 1st as the first day of the year

3: Adding to the code in (1), we can work out the year. Bear in mind that every fourth century begins with a leap year. So you can complete the calculation of the year with the following:

```
  const int DAYS_IN_100_YEARS = (100*365) + 24;
  year += 100 * (N / DAYS_IN_100_YEARS) + (N < DAYS_IN_100_YEARS ? 1 : 0); // Add an extra day for the first leap year that occurs every 400 years.
  N = N - (N < DAYS_IN_100_YEARS ? 1 : 0);
  N = N % DAYS_IN_400_YEARS;
```

4: Now you've sorted out the years, the rest is easy as pie (just remember (2), and the process is easy).

Alternatively you could use boost::date.

Efficient algorithm for converting number of days to years (including leap years)

Solution

Problem

Related problems