question
Devise an algorithm to compute the nearest number that is a palindrome and greater
than the input.
ex. nextPalindrome(10)
returns: 11
ex 2. nextPalindrome(18457)
returns: 18481
ex. nextPalindrome(10)
returns: 11
ex 2. nextPalindrome(18457)
returns: 18481
Try separating the number into two halves to manipulate it.
The best way to solve this in constant time will be to first split the number into
two halves. If the number has odd number of digits, store the middle digit separately.
(ex. 15392 -> 15 & 3 & 93)
Compare reverse of first half of integer with the second half. If reverse(first half) < second half (ex. 15392 -> 51 < 93) then
(1) if number has odd number of digits so there is a middle digit, increment the middle digit by one and append the reverse of first half to the second (ex. 15392 -> 15 & 3 + 1 & reversed(15) = 15451). If the middle digit is 0 then follow step 2 below.
(2) if even number of digits then increment first half by one and append reversed digits to first half and middle digit.
If reverse(first half) = second half, then it is already a palindrome.
If reverse(first half) > second half, simply append the reversed first half to the original first half.
Compare reverse of first half of integer with the second half. If reverse(first half) < second half (ex. 15392 -> 51 < 93) then
(1) if number has odd number of digits so there is a middle digit, increment the middle digit by one and append the reverse of first half to the second (ex. 15392 -> 15 & 3 + 1 & reversed(15) = 15451). If the middle digit is 0 then follow step 2 below.
(2) if even number of digits then increment first half by one and append reversed digits to first half and middle digit.
If reverse(first half) = second half, then it is already a palindrome.
If reverse(first half) > second half, simply append the reversed first half to the original first half.