Consider the following examples
Input Output
3 4
9 11
13 22
767 777
594 595
898 909
999 1001
Here is the solution approach. This problem has multiple cases to be considered.
Case 1:
If all the digits in the number are ‘9’, the output is simply 1 followed by (d-1) 0’s followed by 1, where d is the number of digits in the original number.
Example: 9999, d = 4, so the output is 10001
Case 2:
How do we get a palindrome from a given number with least number of changes?
If the given number itself is a palindrome, obviously we need not make any changes.
Otherwise there are two ways to do that. Replicate the right half with left or replicate the left half with right.
Consider the number 230847, the two possibilities are 230032 and 748847
for 6195824, the two possibilities are 6195916 and 4285824.
Observe that if we replicate left half with right half, we are getting the numbers far from the given number. This is because as we move from right to left, the place value of the digit increases. But we want the number which is just greater than the given number with least difference.
So we have to replicate the right half with left half.
Are we done if we just replace the right half with left half? No.
Let us see the same example of 230847, if we replicate as said above, the result is 230032.
What is the problem with this number? It is a palindrome; but it is smaller than the given number. We wanted a number which is just greater.
So how to make this number just bigger?
Increment the middle digit(s) and propagate the carry if any towards the left and the right.
If the number has even number of digits, there will be two middle digits; otherwise it has just one middle digit.
230032 becomes 231132 and that is the required answer.
Let us consider one more example with carry propagation, 849948. After incrementing middle digits, it becomes 850058.
Here is the C++ implementation of the above algorithm.