"not more than 1000000 digits" means an efficient in-place solution is needed. My first solution was string<->int conversion based. It worked for small ints, but got TLE with large numbers.
Thanks to http://www.bytehood.com/spoj-the-next-palindrome/418/ that shed lights on me. The key idea is the same as my first idea: simply keep increasing digits near the center digit(s), and we only need figure out left half of the digits since it is mirrored palindrome.
(I saw a lot of rejudge requests in SPOJ comments.. several erroneous results got returned from AC code. Mine's also rejected due to wrong answer - I think rejudge is needed)
Corner cases are important to this problem: single digits, all 9s, carry-over situation etc. Here is my code:
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std; int dCarry = ;
int findLgRInx(char *str, int len, int i_l)
{
int i_mis = -;
int i = i_l;
while(i-- >= )
{
if(str[i] > str[len - - i])
{
i_mis = i;
break;
}
}
return i_mis;
} void incLHalf(char *str, int len, int i_l)
{
int i = i_l;
while(i >= )
{
int d = str[i] - '';
if(d < )
{
str[i] = (d + ) + '';
return;
}
else
{
str[i] = '';
if(i > )
{
int nd = str[i-]-'';
if(nd < )
{
str[i-] = (nd + ) + '';
return;
}
}
else
{
dCarry = ;
return;
}
}
i--;
}
} void copyl2r(char *str, int len, int i_l)
{
int i = i_l;
while(i >= )
{
str[len-i-] = str[i];
i--;
}
} void calc_next_palin(char *str)
{
unsigned len = strlen(str);
if(len == )
{
int i = atoi(str);
cout << (i + ) + i / << endl;
return;
} int i_l = , i_r = ;
if(len % == )
{
i_l = len / - ;
i_r = len / ;
int i_mis = findLgRInx(str, len, i_l);
if(i_mis != -)
{
copyl2r(str, len, i_mis);
cout << str << endl;
return;
}
else
{
incLHalf(str, len, i_l);
copyl2r(str, len, i_l);
if(dCarry == )
{
cout << str << endl;
}
else
{
cout << "" << str << "" << endl;
}
return;
}
}
else //odd
{
int i_c = len / ;
int i_mis = findLgRInx(str, len, i_c + );
if(i_mis != -)
{
copyl2r(str, len, i_mis);
cout << str << endl;
}
else
{
int dmid = str[i_c] - '';
if(dmid < )
{
str[i_c] = (dmid + ) + '';
}
else
{
str[i_c] = '';
incLHalf(str, len, i_c - );
copyl2r(str, len, i_c);
}
if(dCarry == )
{
cout << str << endl;
}
else
{
cout << "" << str << "" << endl;
}
}
return;
}
} int main()
{
int cnt; cin >> cnt;
if(cnt == ) return ; //
while(cnt --)
{
string str; cin >> str;
calc_next_palin((char*)str.c_str());
}
return ;
}