Numbers with Distinct Digits
National Olympiad — National round (2009 season)
Submission name: unique.cpp
Problem summary
A number is unique when none of its decimal digits repeat. Count unique numbers in the inclusive interval [m, n]. Zero is a one-digit number.
Input
Two integers m and n.
Output
The number of unique numbers in the interval.
Constraints
0 ≤ m < n ≤ 10,000,000.
Worked example
An independently prepared example for this explanation.
Input
97 104
Output
5
Solution analysis
- Check each integer in the interval. Extract its last digit with remainder by 10 and remove that digit with division by 10.
- Use a ten-element boolean array to record digits already encountered. A repeated digit rejects the number immediately. A do-while loop processes zero as the single digit 0.
- From 97 through 104, the accepted values are 97, 98, 102, 103, and 104. Values 99, 100, and 101 contain repetitions.
Why it works
During a check, seen[d] is true exactly when digit d has already been extracted. A check fails exactly when a repeated digit appears; otherwise every digit is distinct. The outer loop examines every integer of the inclusive interval once, so its count is correct.
Watch out. Include both endpoints. Leading zeros are not part of a number; zero itself must still be considered.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int lower, upper;
cin >> lower >> upper;
int answer = 0;
for (int number = lower; number <= upper; number++) {
bool seen[10] = {};
bool unique = true;
int remaining = number;
// A do-while loop also checks the one-digit number zero.
do {
int digit = remaining % 10;
if (seen[digit]) {
unique = false;
break;
}
seen[digit] = true;
remaining /= 10;
} while (remaining > 0);
if (unique) {
answer++;
}
}
cout << answer << '\n';
}