Distinct Digits in an Interval
National Olympiad — Regional round
Submission name: num.cpp
Problem summary
Count integers in the inclusive interval [a,b] whose decimal digits are pairwise different.
Input
Integers a and b, separated by whitespace.
Output
The qualifying count.
Constraints
0 < a < b < 1,000,000; b−a < 10,000.
Worked example
An independently prepared example for this explanation.
Input
10 22
Output
11
Solution analysis
- Enumerate the short interval.
- For each number, extract digits and reject it as soon as a digit repeats.
Why it works
The digit mask records exactly the already extracted digits, so acceptance is equivalent to pairwise distinct digits. Enumeration covers both endpoints.
Complexity: O((b−a+1) log b) time, O(1) space.
Watch out. Leading zeros are not digits of the number.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The digit mask records exactly the already extracted digits, so acceptance is equivalent
// to pairwise distinct digits. Enumeration covers both endpoints.
#include<iostream>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
int ans=0;
for(int x=a;x<=b;x++){
int y=x,mask=0;
bool ok=true;
while(y){
int d=y%10;
y/=10;
if(mask&(1<<d)){
ok=false;
break;
}
mask|=1<<d;
}
ans+=ok;
}
cout<<ans<<'\n';
}