Even Digits
National Olympiad — Municipal round
Submission name: chet.cpp
Problem summary
Find the largest nonnegative integer strictly smaller than N whose decimal digits are all even.
Input
One positive decimal integer N.
Output
The greatest all-even-digit integer below N; output 0 when it is the answer.
Constraints
N has at most 100 decimal digits.
Worked example
An independently prepared example for this explanation.
Input
301
Output
288
Solution analysis
- First subtract one using decimal-string arithmetic, turning strict inequality into a ≤ bound.
- Scan the resulting bound from left to right. If every digit is even, it is already the answer.
- At the first odd digit, reduce it by 1 to the next smaller even digit. Fill every following position with 8.
- Remove leading zeros, but keep a single zero if all digits become zero.
Why it works
The prefix before the first odd digit is kept as large as possible. That odd digit cannot remain; lowering it to the closest even digit preserves the largest feasible prefix. After that decrease, any suffix is below the bound, so all 8s maximize it.
Watch out. The answer must be strictly smaller: an already-all-even N is not itself allowed. Ordinary integer types cannot hold 100 digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
cin>>s;
// Compute N-1 without converting the large number to an integer.
int i=(int)s.size()-1;
while(s[i]=='0'){
s[i]='9';
--i;
}
--s[i];
for(int j=0;j<(int)s.size();++j){
if((s[j]-'0')%2){
--s[j]; // Odd digit -> greatest even digit below it.
for(int k=j+1;k<(int)s.size();++k){
s[k]='8';
}
break;
}
}
auto first=s.find_first_not_of('0');
cout<<(first==string::npos?"0":s.substr(first))<<'\n';
}