problem564

README

< Previous 　　　　　　　　　　　　　　　　 Next >

564. Find the Closest Palindrome (Hard)

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

 

Example 1:

Input: n = "123"
Output: "121"

Example 2:

Input: n = "1"
Output: "0"
Explanation: 0 and 2 are the closest palindromes but we return the smallest which is 0.

 

Constraints:

• 1 <= n.length <= 18
• n consists of only digits.
• n does not have leading zeros.
• n is representing an integer in the range [1, 1018 - 1].

Related Topics

[Math] [String]

Hints

Hint 1

Will brute force work for this problem? Think of something else.

Hint 2

Take some examples like 1234, 999,1000, etc and check their closest palindromes. How many different cases are possible?

Hint 3

Do we have to consider only left half or right half of the string or both?

Hint 4

Try to find the closest palindrome of these numbers- 12932, 99800, 12120. Did you observe something?