SPOJ 5. The Next Palindrome Problem code: PALIN

This problem has several traps.

The solution to the problem is to understand the answer to the question :

“If I am allowed to change a digit in a number (to make it a palindrome) which digit should I change in order to change the given number as little as possible?”

The idea:

Let the given number be 123321. Let’s try to get the next palindrome.

First, we try changing the rightmost digit (1) to 2, then we need to change also the leftmost digit (1) to 2 in order to make it a palindrome. But the leftmost digit of any number is the most significant digit. Changing it will change the number by the highest possible amount. So, we don’t want that.

So, we can see that we need to change the middle digits so that we get the “smallest palindrome larger than the given number” as asked in the problem statement. Therefore the idea is to start in the middle and change digits in both directions outwards to make the palindrome.

This is how we get the next palindrome:

123321 --> 124421

For the sample inputs given in the problem statement:

808 --> 818

2133 --> 2223 --> 2222

Some special inputs:

0 --> 1

9 --> 11

99 --> 101

Points to note:

1. Each number given as input can be as long as 1000000 digits. This means that you cannot use any available data types like int or double. You need to store the number in an array of chars. Note: Remember to give the size of the array as 1000001 or more. Because a 1000000 digit number occupies 1000000 chars + 1 char for the null (string termination).

2. Try inputs of both even and odd length numbers.