smallest number greater than given number which is a palindrome

Question

This was asked in an interview. Given a number, say 900, output the smallest palindrome greater than the number, 909 in this case. I gave a brute force solution that checks every number but I'm assuming there's a better way to go about this

Answer 1

Copy the first digit to the last, second digit to the second-last etc until you reach the center digit (or center 2 digits if there is an even number of digits).

If the resulting number is smaller than the original number, increase the center digit/center 2 digits by one. If they are 9, set them to zero and retry with the 2 digits next to them, moving outwards until you hit a non-9.

Edit:

If the loop that moves outwards never hits a non-9, prepend a 1 to the string, set all digits except the last one to 0, and the last one to 1. This is the same as adding 2 to the number.