SPOJ; The Next Palindrome

This problem asks for next integer that is also a palindrome, after a given integer. A naive approach would be to start iterating over integers after the given one, and see if you hit a palindrome. Whenever you do, that is your answer. But the problem is that given input can have 1000000 digits. Iterating over integers that big to find a palindrome is going to take eons, besides the fact that you can’t even represent that big a number with a primitive type.

Solution:

We are going to use string operations to generate next palindrome. Notice that a palindrome is identified by its left half digits. If you know the first half of the integer, the second half is just a mirror of the first half.

We start by first generating a palindrome out of the given input, by mirroring first half portion over to the second half, around the center. This will give us a palindrome that is closest to the input number. Any palindrome which changes any digit of the first half of the given input, will take us farther away from our given integer in either directions.

E.g. if input is 39474657, we change it to 39477493.

Now that we have a palindrome which is closest to given input, we just incrementally generate higher palindromes, till we have a number that is higher than our input. In order to do this, we increment the center digit. If it is an even sized integer, there are two digits in the center. Remember that as soon as we increment the center digit, we will have a palindrome that is next higher than our existing one. Only caveat is that if the center digit is a ‘9’. In which case we change it to ‘0’, and increment the next digit to the left (also incrementing its mirror digit to the right). If next digit is ‘9’ too, we keep on performing this operation till we hit a digit that isn’t a ‘9’. It is possible that we encounter all digits as ‘9’, in which case, we add a ‘1’ to left of our input, while incrementing the right most ‘0’ as generated by previous operations, to a ‘1’.

Be Sociable, Share!

One thought on “SPOJ; The Next Palindrome

Leave a Reply