The idea of this problem is to find the immediate next palindrome of a given number. When I submit it to online judge on SPOJ it gives wrong answer. I have tested the code for all possible boundary and exception cases I can think of but still can't figure out which test case my code is failing. I will be very very grateful to you if you can figure out any test case that is not satisfied.
#include<iostream>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdio.h>
using namespace std;
bool all_nine(string s,long long size)
{
long long count=0;
for(long long i=0;i<s.length();i++)
{
if(s[i]=='9')
count++;
else
return false;
}
return true;
}
void copy(string &low,string &high)
{
long long j=0;
for(long long i=low.size()-1;i>=0;i--)
{
high[j]=low[i];
j++;
}
}
void increment(string &low)
{
int size=low.length();
stringstream convert(low);
long long temp=0;
convert>>temp;
temp+=1;
ostringstream str1;
str1<<temp;
low=str1.str();
if(low.length()<size)
{
int temp=size-low.length();
string s1;
for(int i=0;i<temp;i++)
{
s1+="0";
}
low=s1+low;
}
}
string find_next_palindrome(string s)
{
//cout<<s;
long long size=s.length();
//cout<<"size:"<<size;
if(all_nine(s,size))
{
s[0]='1';
for(long long i=1;i<size;i++)
s[i]='0';
s+='1';
return s;
}
else if(size%2==0)
{
string low,high;
long long mid=size/2;
for(long long i=0;i<mid;i++)
low+=s[i];
for(long long i=mid;i<size;i++)
high+=s[i];
if((long long)s[mid-1]>(long long)s[mid])
{
copy(low,high);
}
else if((long long)s[mid-1]<(long long)s[mid])
{
increment(low);
copy(low,high);
}
else
{
long long temp_low=mid-1;
long long temp_high=mid;
while(temp_low!=0 && temp_high!=size-1)
{
if((long long)s[temp_low]>(long long)s[temp_high])
break;
temp_low--;
temp_high++;
}
if((long long)s[temp_low]>(long long)s[temp_high])
{
copy(low,high);
}
else
{
increment(low);
copy(low,high);
}
}
return low+high;
}
else
{
string low,high;
long long mid=size/2;
for(long long i=0;i<mid;i++)
low+=s[i];
for(long long i=mid+1;i<size;i++)
high+=s[i];
if((long long)s[mid-1]>(long long)s[mid+1])
{
copy(low,high);
}
else if((long long)s[mid-1]<(long long)s[mid+1])
{
if(s[mid]=='9')
{
s[mid]='0';
increment(low);
copy(low,high);
}
else
{
s[mid]=((s[mid]-'0')+1)+'0';
copy(low,high);
}
}
else
{
long long temp_low=mid-1;
long long temp_high=mid+1;
while(temp_low!=0 && temp_high!=size-1)
{
if((long long)s[temp_low]!=(long long)s[temp_high])
break;
temp_low--;
temp_high++;
}
if((long long)s[temp_low]>(long long)s[temp_high])
{
copy(low,high);
}
else
{
if(s[mid]=='9')
{
s[mid]='0';
increment(low);
copy(low,high);
}
else
{
s[mid]=((s[mid]-'0')+1)+'0';
copy(low,high);
}
}
}
return (low+s[mid]+high);
}
}
int main()
{
long long t;
cin>>t;
vector<string> v(t);
for(long long i=0;i<t;i++)
{
string temp;
cin>>temp;
v[i]=temp;
}
//cout<<"\n"<<"\n";
for(long long i=0;i<t;i++)
{
if(v[i].length()==1)
{
if(v[i]=="9")
cout<<"11"<<endl;
else
cout<<(v[i][0]-'0')+1<<endl;
}
else
{
string str=find_next_palindrome(v[i]);
for(long long j=0;j<str.length();j++)
cout<<str[j];
cout<<"\n";
}
}
return 0;
}
Test input:
40
808
2133
9999999
999999
899998
3423355356
100001
46887767
9
99
0
1991
1239400
123999500
56442
56471
123456
1234567
77777777777
2991
3994
9999
5448
653434
101
199
0012100
0003
123456
1234567
9999
99999
1
2991
3994
9999
5448
65343454
100
4111
Expected output:
818
2222
10000001
1000001
900009
3423443243
101101
46888864
11
101
1
2002
1240421
124000421
56465
56565
124421
1235321
77777877777
2992
4004
10001
5555
654456
111
202
0013100
0110
124421
1235321
10001
100001
2
2992
4004
10001
5555
65344356
101
4114
My program gives the expected output, so I can't figure out why it is marked as not correct. Is there another case not covered in the model input for which my program doesn't give the correct answer?
