Almost Repeated Digits
Autumn Tournament (2022)
Submission name: numbers.cpp
Problem summary
Given x, find the smallest y≥x whose decimal digits are all equal. When k=1, allow at most one digit to differ from the others. Leading zeroes are not allowed.
Input
The integer x, then k (0 or 1).
Output
The smallest valid integer y≥x.
Constraints
100 ≤ x ≤ 10^17.
Worked example
Original statement sample.
Input
700 1
Output
700
Solution analysis
- Let L be the number of digits in x. It suffices to search L-digit candidates: the number consisting of L nines is always valid and at least x, so no longer answer is needed.
- Choose a repeated digit from 0 through 9 and fill an L-character string with it. If k=0, test only that string. If k=1, also choose the exceptional position and its digit from 0 through 9. This includes all-equal candidates when the replacement is unchanged. Reject any candidate starting with zero, convert to a 64-bit integer, and keep the smallest value at least x.
- For x=700,k=0 the first valid repeated-digit number not below x is 777. With k=1, 700 itself is allowed: zero is the repeated digit and the leading 7 is the single exception. This is why the base repeated digit must be allowed to be zero.
Why it works
Every allowed number either has a single repeated digit everywhere, or has a repeated digit and at most one exceptional position. Enumeration covers exactly these choices, discards invalid leading-zero forms, and takes the minimum candidate above the threshold. Existence of the all-nines candidate proves that searching only L digits is sufficient.
Watch out. Do not omit base digit zero: numbers such as 700 are valid in the good-mood case. Do not use floating-point powers of ten. The condition allows at most one exception, not exactly one.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int main(){
long long lower;
int allowedException;
cin>>lower>>allowedException;
int length=static_cast<int>(to_string(lower).size());
long long answer=stoll(string(length,'9'));
auto consider=[&](const string&candidate){
if(candidate[0]=='0'){
return;
}
long long value=stoll(candidate);
if(value>=lower){
answer=min(answer,value);
}
};
// Zero must be allowed as the repeated digit, as in 700.
for(char repeated='0';repeated<='9';repeated++){
string candidate(length,repeated);
consider(candidate);
if(allowedException==0){
continue;
}
for(int position=0;position<length;position++){
for(char replacement='0';replacement<='9';replacement++){
candidate[position]=replacement;
consider(candidate);
}
candidate[position]=repeated;
}
}
cout<<answer<<'\n';
}