Exactly One, Two or Three Trailing Zeros
National Olympiad — Municipal round (2026 season)
Submission name: zeros.cpp
Problem summary
In the inclusive interval [a,b], count separately the integers ending in exactly one, exactly two, and exactly three decimal zeros.
Input
Two positive integers a and b.
Output
Three lines: the counts for exactly 1, 2 and 3 trailing zeros, respectively.
Constraints
0 < a < b < 500,000,000.
Worked example
An independently prepared example for this explanation.
Input
95 205
Output
9 2 0
Solution analysis
- A number has at least t trailing zeros exactly when it is divisible by 10^t. The number of multiples of d in [a,b] is floor(b/d) − floor((a−1)/d).
- To obtain exactly t zeros, subtract the multiples of 10^(t+1) from the multiples of 10^t. This removes every number with any larger number of trailing zeros.
- For [95,205], there are 11 multiples of 10 and 2 multiples of 100, giving 9 numbers with exactly one trailing zero. The two multiples of 100 are 100 and 200; neither is a multiple of 1000. Thus the three answers are 9, 2, 0.
Why it works
Multiples of 10^(t+1) form a subset of multiples of 10^t. Removing that subset leaves precisely the numbers divisible by the smaller power but not the larger one, which is the definition of exactly t trailing zeros.
Watch out. Include both endpoints by using a−1 in the prefix subtraction. Do not enumerate up to 500 million numbers. For exactly three zeros, also subtract multiples of 10000.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int countMultiples(int left, int right, int divisor) {
return right / divisor - (left - 1) / divisor;
}
int main() {
int left, right;
cin >> left >> right;
int powerOfTen = 10;
for (int zeros = 1; zeros <= 3; zeros++) {
int atLeastThisMany = countMultiples(left, right, powerOfTen);
int atLeastOneMore = countMultiples(left, right, powerOfTen * 10);
cout << atLeastThisMany - atLeastOneMore << '\n';
powerOfTen *= 10;
}
}