Count Leap Years in a Range
Problem
Read two years a and b (a <= b). Print how many leap years there are from year a to year b, both included. A year is a leap year if it is divisible by 4, except years divisible by 100 that are not divisible by 400. Use a formula, not a loop.
Constraints
- 1 <= a <= b <= 9999
Examples
Input
2000 2024
Output
7
Solutions
Counting multiples with integer division is O(1). Looping over every year would also work but is slower for large ranges. The same idea (count up to b, subtract count before a) works for many range counting problems.
/*
* Problem : Count leap years.
* Input : Two years a and b.
* Output : The count.
* Approach: Counting multiples.
* Time : O(1)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static long solve(long a, long b) {
// Step 1: leapUpTo(y) counts the leap years from year 1 to year y: multiples of 4, minus multiples of 100, plus multiples of 400.
// Step 2: The leap years from a to b are leapUpTo(b) - leapUpTo(a - 1).
long upToB = b / 4 - b / 100 + b / 400;
long beforeA = (a - 1) / 4 - (a - 1) / 100 + (a - 1) / 400;
return upToB - beforeA;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
System.out.println(solve(a, b));
}
}
Hints (1)
- Which years divisible by 100 are leap years?