Algorithm Practice: Given an Integer, Find the Next Closest Integer that is a Palindrome

Some cases to think about:
1. input number is all nines, 999 => 1001
2. input number is not a palindrome, 1234 => 1331
3. input number is a palindrome and is not all nines, 1221 => 1331

My thinking is that we can split up the number into two halves, and just compare the left side to the reverse of the right side. If you start with the right side, the next palindrome formed is not guaranteed to be larger. So let’s start by evaluating and incrementing the left side. Let’s say we’re evaluating the number 1234. We split the number in half , 12, and then mirror it to be 1221.

Since that number is not larger than our input, we need to increment the last number on the left-hand side and create a palindrome from that. We’ll go from 1221 to 1331:

And then pulling it all together:

get_next_palindrome(23) // 33
get_next_palindrome(999) // 1001
get_next_palindrome(1234) // 1331
get_next_palindrome(1221) // 1331
get_next_palindrome(100) // 101
get_next_palindrome(890) // 898
get_next_palindrome(999999) // 1000001