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 <= 18n consists of only digits.n does not have leading zeros.n is representing an integer in the range [1, 1018 - 1].class Solution {
public String nearestPalindromic(String n) {
int len = n.length(), mid = len % 2 == 0 ? len / 2 - 1 : len / 2;
long N = Long.valueOf(n), firstHalf = Long.valueOf(n.substring(0, mid + 1));
long[] pals = new long[5];
pals[0] = makePalindrome(firstHalf, len % 2 == 1);
pals[1] = makePalindrome(firstHalf - 1, len % 2 == 1);
pals[2] = makePalindrome(firstHalf + 1, len % 2 == 1);
pals[3] = (long) Math.pow(10, len - 1) - 1;
pals[4] = (long) Math.pow(10, len) + 1;
// System.out.println(Arrays.toString(pals));
long minDiff = Long.MAX_VALUE, ans = pals[0];
for (long p : pals) {
if (p == N)
continue;
long currDiff = Math.abs(N - p);
if (minDiff > currDiff) {
minDiff = currDiff;
ans = p;
} else if (minDiff == currDiff) {
ans = Math.min(ans, p);
}
}
return String.valueOf(ans);
}
private long makePalindrome(long half, boolean odd) {
long pal = half;
if (odd)
half /= 10;
while (half > 0) {
pal = pal * 10 + (half % 10);
half /= 10;
}
return pal;
}
}