Next Smallest Palindrome

Given a number, we have to find the next smallest palindrome which is larger than this number. 

The input can be large. We'll store the input in an array. e.g. if input is  1259,
array will be, int k[]= {1,2,5,9}
To find the next smallest palindrome, we have to generalize the input. There can be three types of input.  

1. All digits are 9. e.g. 999
2. Input is not a palindrome. e.g 12942
3. The input itself a palindrome number. e.g. 1221

Algorithm for the first type is easy. Expand the array length by one and put boundary digits as 1 & all other digits will be 0. 

Input:   999

Output: 1001

 

Left half & Right half: Using example, left half of 522665 is, 522 & left half of 52123 is 52. Right half of 522665 is 665 & right half of 52123 is 23.  

Iteration: We'll compare between left half and right half, starting from middle. For example, two variable i and j will indicate to 2 & 4 respectively, if the input is 1 2 2 4 2 and i and j will indicate to 9 & 3 respectively if the input is 5 6 9 3 2 5. For each iteration i will decrement and j will increment.

Comparison outcomes.

• k[i] == k[j] if this is true, do nothing.
• k[i] > k[j] if this is true, then stop comparing and just copy left half to right half.
• k[i] < k[j] if this is true, follow the procedure below.

Add and Copy: Add 1 to middle digit & propagate carry to the left half and simultaneously copy left half to right half.

Input: 5 2 1 1 6 5

n is even. so middle digit is 1 of left half. Perform (1+1) . 

summation 2, carry 0.

X X 2 2 X X

X 2 2 2 2 X

5 2 2 2 2 5

Output: 5 2 2 2 2 5

Input: 1 2 9 4 5

middle digit is 9. add 1 to it. propagate carry to left half and copy to right half simultaneously.

X X 0 X X

 X 3 0 3 X

1 3 0 3 1

Output: 1 3 0 3 1

#type 3: For all iterations, k[i] == k[j]. It means the input is palindromic. To find the next smallest palindrome, follow the same procedure as before. add 1 to middle digit and copy from left to right simultaneously.