PALIN - The Next Palindrome


A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133

Output:
818
2222

Warning: large Input/Output data, be careful with certain languages


hide comments
akash9827: 2018-01-06 05:32:10

I did this by reversing the number , i've checked corner cases too , all are correct.
but then too i'm getting wrong answer.
NOTE---->>> I've taken input as "unsigned long int", do i need to take input as a string and then do the processing??

mona_coder: 2017-12-28 11:56:16

integer K of not more than 1000000 digits; why it is showing wrong answer?

pust_coder: 2017-12-28 11:04:14

what is wrong of this problem??please ans me,,
#include<iostream>
using namespace std;
int main()
{
unsigned long long int n,k,sum,m;
int t,i,j,mod;
cin>>t;
for(i=0;i<t;i++)
{
cin>>n;
for(j=0;j<n;j++){
sum=0;
n=n+1;
k=n;
m=n;
while(m>0)
{

mod=m%10;
sum=sum*10+mod;
m=m/10;
}
if(sum==k){
cout<<sum<<endl;
break;
}

}
}
}

nadstratosfer: 2017-12-23 23:55:15

TL is very lenient by SPOJ standards, and friendly for slower languages. I even got AC with a hastily put together semi-bruteforce in 3.45s while a proper solution took 0.05s. Good problem for beginners to learn about efficiency of very common operations and pick up some good practices.

ystm: 2017-12-22 17:01:36

I wrote same algorithm in python and rust, but only rust passed. If you've got TLE in slow language, consider to choose another faster one.

bigbrobd: 2017-12-21 22:28:48

Following test cases r correct..
Still says wrong answer.. I cant understand what is happening.

Input :
22
19091919191
1999991
121
100
890
1221
123450000004
0
808
2133
11111111111111111111
11111111111111111111111111111111111111111
1119191991900234245239919234772376189636415308431
99
999999
241342191
374294242
242343242
898
77777
888888
13413515134000000000000000013488097081324

Output :
19092029091
2000002
131
101
898
1331
123450054321
1
818
2222
11111111122111111111
11111111111111111111211111111111111111111
1119191991900234245239920299325424320091991919111
101
1000001
241343142
374303473
242353242
909
77877
889988
13413515134000000000100000000043151531431

Last edit: 2017-12-21 22:29:24
snitesh24: 2017-12-13 20:14:48

Accepted after passing below testcases..
Input :
22
19091919191
1999991
121
100
890
1221
123450000004
0
808
2133
11111111111111111111
11111111111111111111111111111111111111111
1119191991900234245239919234772376189636415308431
99
999999
241342191
374294242
242343242
898
77777
888888
13413515134000000000000000013488097081324

Output :
19092029091
2000002
131
101
898
1331
123450054321
1
818
2222
11111111122111111111
11111111111111111111211111111111111111111
1119191991900234245239920299325424320091991919111
101
1000001
241343142
374303473
242353242
909
77877
889988
13413515134000000000100000000043151531431

aar_em: 2017-12-12 14:19:41

It works for manually entered inputs, why does it show here wrong answer?

saikumarm4: 2017-12-05 14:33:45

how does Wrong answer is decided ? Does it consider time and space complexity also ? or only after looking at the test cases ?@prothlete even I am facing same issue, did you by any chance resolved it ? it works in my IDE and fails online

Last edit: 2017-12-05 17:31:11
code_killerx: 2017-12-04 06:28:56

Getting a WA in this code don't know why pls help https://ideone.com/4t9xJa


Added by:adrian
Date:2004-05-01
Time limit:2s-9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6

Problem's scores 1 vote

Concept difficulty
Concept difficulty 37%
Implementation difficulty
Implementation difficulty 50%
458 16