Next Number with Distinct Digits
Autumn Tournament (2013)
Submission name: next.cpp
Problem summary
For each nonnegative integer A, find the smallest integer strictly greater than A whose decimal digits are all distinct. Print −1 if none exists.
Input
N, followed by N nonnegative integers.
Output
One answer per input number, or −1.
Constraints
1 ≤ N ≤ 100; 0 ≤ A ≤ 10^12.
Worked example
Original statement sample.
Input
4 42 10 424242424242 426661337
Output
43 12 -1 426701358
Solution analysis
- A valid answer has at most ten digits. First try the same length as A. Build digits from left to right, trying unused digits in increasing order. A flag records whether the chosen prefix is already larger; while equal, a candidate digit must be at least the corresponding digit of A.
- As soon as a prefix is larger, all remaining positions can use the smallest available digits. Backtracking is only needed along equal prefixes or when the current position has no permitted digit. If the same length fails, the smallest distinct-digit number of the next length is 1023…; no length beyond ten is possible.
- For 10, retaining prefix 1 forces the last digit to exceed 0, and digit 1 is already used. The next usable choice is 2, producing 12. For 426661337, the first repeated 6 forces backtracking: increasing the appropriate prefix and filling the suffix with the smallest unused digits gives 426701358.
Why it works
Every same-length number greater than A follows a prefix that is equal until its first larger digit, then remains unrestricted except for unused digits. The search enumerates these choices in lexicographic order, so its first complete result is the smallest. A longer positive decimal number is greater than any shorter one; the first feasible longer length is therefore optimal.
Watch out. The comparison is strict, so the original number itself is not an answer. Zero cannot be a leading digit in a multi-digit number. Values larger than the ten-digit maximum cannot have a successor. Keep the answer as a string.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
bool build(const string&bound,int position,int used,bool greater,string&answer){
if(position==static_cast<int>(bound.size())){
return greater;
}
int minimum=greater?0:bound[position]-'0';
for(int digit=minimum;digit<=9;digit++){
if((used&(1<<digit))||(position==0&&digit==0&&bound.size()>1)){
continue;
}
answer.push_back(static_cast<char>('0'+digit));
// Once greater, every unused digit is allowed in the suffix.
if(build(bound,position+1,used|(1<<digit),greater||digit>minimum,answer)){
return true;
}
answer.pop_back();
}
return false;
}
int main(){
int queries;
cin>>queries;
while(queries--){
string bound;
cin>>bound;
string answer;
if(bound.size()<=10&&build(bound,0,0,false,answer)){
cout<<answer<<'\n';
}
else if(bound.size()<10){
string smallest="1023456789";
cout<<smallest.substr(0,bound.size()+1)<<'\n';
}
else{
cout<<-1<<'\n';
}
}
}