Pages with Repeated Digits
National Olympiad — Regional round (2020 season)
Submission name: beautiful.cpp
Problem summary
A book has pages numbered from 1 through N. A page number is beautiful if all of its decimal digits are identical. Count the beautiful pages.
Input
One integer N.
Output
The number of beautiful page numbers not exceeding N.
Constraints
1 ≤ N ≤ 1000000000000000000.
Worked example
An independently prepared example for this explanation.
Input
30
Output
11
Solution analysis
- Every positive beautiful number is formed by choosing one digit d from 1 through 9 and repeating it some number of times. Zero cannot begin a positive page number.
- For each d, start at d and repeatedly append another d using value=10·value+d. Count every generated value at most N. Before appending, test whether value>(N−d)/10; if so, the next candidate would exceed N and generation can stop safely.
- For N=30, all nine one-digit pages qualify, along with 11 and 22. The next two-digit candidate 33 is already too large, giving 11 beautiful pages in total.
Why it works
Each generated number uses only one repeated nonzero digit and is therefore beautiful. Conversely, every positive beautiful number has a unique repeated digit and length, so it appears in exactly one generation loop. The bound check counts exactly those at most N, with no duplicates.
Watch out. Do not count page zero. Guard the append operation so no overflowing next candidate is constructed.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
long long n;
cin >> n;
int answer = 0;
for (int digit = 1; digit <= 9; ++digit) {
long long value = digit;
while (value <= n) {
++answer;
// Test the next append using division, avoiding overflow.
if (value > (n - digit) / 10) {
break;
}
value = value * 10 + digit;
}
}
cout << answer << '\n';
}