This is my solution to the problem. I can’t seem to find the corner cases for this sum.
My submission: CodeChef: Practical coding for everyone
i checked my solution for 1 till 10000 (using python code)
I used diff to see the difference and i could not find any differences in the output of these two codes (cpp code is the final code which i submitted):
python code for testing:
for n in xrange(1,10000+1):
res = 1
for i in xrange(1,n+1):
number = i
res = max(res,int(str(number)[::-1]))
print res
cpp code:
#include <bits/stdc++.h>
using namespace std;
bool all9(string &str,int k){
int flag = 0;
for(int i=k;i<str.size();++i){
if(str[i] != '9')
return false;
}
return true;
}
int main(){
int t;
cin >> t;
while(t--){
string str;
cin >> str;
if(str.size()==1){
cout << str << endl;
continue;
}
int flag9 = 0, flag0 = 0;
for(int i=0;i<str.size();++i)
if(str[i] == '9')
flag9++;
else if(str[i] == '0')
flag0++;
if(flag9 == str.size()){
cout << str << endl;
continue;
}
if(str[0]=='1' && flag0 == str.size()-1){
cout << std::string(str.size()-1,'9') << endl;
continue;
}
if(all9(str,1)){
reverse(str.begin(),str.end());
cout << str << endl;
continue;
}
if((str[0]-'0')>1){
str[0] = ((str[0]-'0')-1) + '0';
for(int i=1;i<str.size();++i) str[i] = '9';
reverse(str.begin(),str.end());
cout << str << endl;
continue;
}
else{
int flag = 0;
for(int i=1;i<str.size()-1;++i){
if((str[i]-'0')>1 && !all9(str,i+1)){
str[i] = ((str[i]-'0')-1) + '0';
for(int j=i+1;j<str.size();++j) str[j] = '9';
reverse(str.begin(),str.end());
cout << str << endl;
flag = 1;
break;
}
else if((str[i]-'0')==1 && !all9(str,i+1)){
str[i] = '0';
for(int j=i+1;j<str.size();++j) str[j] = '9';
reverse(str.begin(),str.end());
cout << str << endl;
flag = 1;
break;
}
}
if(flag == 0){
reverse(str.begin(),str.end());
cout << str << endl;
}
}
}
return 0;
}