Input

The first line contains integer t, the number of test cases. Followed by t lines containing integers K.

Output

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

Example

Input:

2

808

2133

Output:

818

2222

Response1:

If ( (number already a palindrome) or (right half <> left half)

___ Copy reverse of left half to right half.

Response2:

perfect..above soln always gives correct answer.

for even no.of digits join n/2,n/2+1 th digit as one digit(so that u've to increment both these digits for 1st case).

ex.1441

ans->> 1551(if i'm not wrong)

here both the digits(2nd ,3rd).

this may also be done using naive approach like

while(!ispalindrome(++n))

;

output(n)

but this consumes a lot computing time.u can verify this

by giving large nos as i/p.

Response3:

the solution is not correct...

consider the case say 323421

now the right half ie 421 is greater than left 323

so according to your algo the answer wud be 323323

which is wrong...

the correct algo is

If ( (number already a palindrome) or (right half <> left half)

___increment the last digit of left half by 1 and copy the reverse of it to right half.

Response4:

>> In case of even length.. middle element is the rightmost element of left half.

>> otherwise middle element is separate from left half.

So, the correct algo goes like..

If( reverse left half> right half )

___ Copy reverse left half to right half

else

___ Increment middle element by 1 and then Copy reverse left half to right half.

Response5:

Modified algo

For even digits

increment left half until left half

copy left half to right half

I support Response3:

ReplyDeletethe solution is not correct...

consider the case say 323421

now the right half ie 421 is greater than left 323

so according to your algo the answer wud be 323323

which is wrong...

the correct algo is

If ( (number already a palindrome) or (right half <> left half)

___increment the last digit of left half by 1 and copy the reverse of it to right half.

Chaise Lounge Declared: "I think the solution is correct."

ReplyDeleteBena Windows vista - Probably the most Attractive Attributes

ReplyDeleteMy website; cherub