Find the Closest Palindrome

Hard · Math & Number Theory · about 35 minutes

Asked at Google, Amazon, Microsoft, Meta.

n is an integer written as a string. Find the palindromic integer nearest to it, other than n itself, and return it as a string. If two are equally near, return the smaller.