problem564

README

< Previous 　　　　　　　　　　　　　　　　 Next >

564. Find the Closest Palindrome (Hard)

Given an integer n, find the closest integer (not including itself), which is a palindrome.

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

Example 1:

Input: "123"
Output: "121"

Note:

1. The input n is a positive integer represented by string, whose length will not exceed 18.
2. If there is a tie, return the smaller one as answer.

Related Topics

[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?