https://www.spoj.com/problems/PALIN/
I am trying to understand the intuition behind why this algorithm actually works.
Problem statement:
Given a number $N\le10^5$ generate the palindrome just after it.
For example:
$613745$ => $614416$
Algorithm:
- Divide the number into 2 halves. Two halves because a palindrome's 2nd half is the reverse of the 1st half.
- If the number is even, if the rightmost digit of the left half is less than the leftmost digit of the right half then increment the left half and reverse it to make the right half. Else if the rightmost digit of the left half is greater than the leftmost digit of the right half then just reverse the left half to make the right half.
- If the number is odd, then reverse the 1st half and make that reversed 1st half the 2nd half. Check if the number is greater than original input, if not increment the middle digit (adjust for carry) and try again.
- If equal just expand outwards.
Example for odd cases:
808 => 818
901 => 909
I understand how the algorithm works but I do not understand why it is guaranteed to give the smallest palindrome larger than $N$.
What my intuition says so far:
Since we are incrementing a digit that is present in the left half, we know that the value of the number will increase. Also if the left last digit is greater than the right first digit then we just copy over the reversed version of the left side, and thus limiting the increase of the number.
But none of these steps explain why it is guaranteed to give the smallest palindrome larger than $N$.
Is there a way to prove the correctness of the algorithm ?