Find the Closest Palindrome

Given a positive integer num as a string (at most 15 digits), return the closest integer that is a palindrome, not counting num itself. If two palindromes are equally close, return the smaller one.

LeetCode: 564. Find the Closest Palindrome

Example

Input: "99"     Output: "101"   (88 and 101 are both palindromes; 101 is 2 away, 88 is 11)
Input: "123"    Output: "121"
Input: "1"      Output: "0"
Input: "10"     Output: "9"     (9 and 11 are both 1 away; 9 is smaller)

Brute force: step outwards

Check n - 1, n + 1, n - 2, n + 2, and so on. The first palindrome found is the closest, and checking the smaller side first handles ties.

A 15-digit number does not fit in an int, so the code uses long, a 64-bit integer. Long.parseLong converts the string, and long holds values up to about 9.2 * 10^18, which covers every 15-digit input and the 16-digit answers. Integer arithmetic would wrap around silently on overflow.

public class Main {
    static boolean isPalindrome(long x) {
        String s = Long.toString(x);
        return new StringBuilder(s).reverse().toString().equals(s);
    }

    static String nearestPalindrome(String num) {
        long n = Long.parseLong(num);
        for (long d = 1; ; d++) {
            if (n - d >= 0 && isPalindrome(n - d)) return Long.toString(n - d);
            if (isPalindrome(n + d)) return Long.toString(n + d);
        }
    }

    public static void main(String[] args) {
        for (String num : new String[]{"99", "123", "1", "10", "12932"}) {
            System.out.println(num + " -> " + nearestPalindrome(num));
        }
    }
}

99 -> 101
123 -> 121
1 -> 0
10 -> 9
12932 -> 12921

Time: up to O(√n · d) for d digits, because consecutive palindromes can be about √n apart. For a 15-digit number, that's millions of checks. Space: O(d).

Optimal: five candidates

The closest palindrome keeps as much of the high-order half as possible. Take the left half including the middle digit (prefix), and mirror it onto the right. Changing the middle of the prefix by one gives the nearest palindromes on either side:

1. prefix mirrored: 12932 → prefix 129 → 12921
2. prefix - 1 mirrored: 128 → 12821
3. prefix + 1 mirrored: 130 → 13031

Mirroring can't change the digit count, so two more candidates cover the jump between lengths:

4. 10^(d-1) - 1, the largest palindrome with one digit fewer (99 for d = 3, needed for 100 → 99)
5. 10^d + 1, the smallest palindrome with one digit more (1001 for d = 3, needed for 999 → 1001)

Pick the candidate that isn't num itself and has the smallest distance, breaking ties by the smaller value. The comparison uses Math.abs on a long difference, which cannot overflow here, and it avoids Long.MIN_VALUE, the one value whose Math.abs stays negative.

public class Main {
    static long mirror(long prefix, int len) {
        String left = Long.toString(prefix);
        // for an odd length, skip the middle digit so it is not repeated
        String right = new StringBuilder(left).reverse().substring(len % 2);
        return Long.parseLong(left + right);
    }

    static long pow10(int exp) {
        long result = 1;
        for (int i = 0; i < exp; i++) result *= 10;
        return result;
    }

    static String nearestPalindrome(String num) {
        long n = Long.parseLong(num);
        int len = num.length();
        long prefix = Long.parseLong(num.substring(0, (len + 1) / 2));
        long[] candidates = {
            mirror(prefix, len),
            mirror(prefix - 1, len),
            mirror(prefix + 1, len),
            pow10(len - 1) - 1,
            pow10(len) + 1,
        };
        long best = -1;
        for (long c : candidates) {
            if (c == n) continue;
            if (best == -1
                    || Math.abs(c - n) < Math.abs(best - n)
                    || (Math.abs(c - n) == Math.abs(best - n) && c < best)) {
                best = c;
            }
        }
        return Long.toString(best);
    }

    public static void main(String[] args) {
        for (String num : new String[]{"99", "123", "1", "10", "12932", "100", "999999999999999"}) {
            System.out.println(num + " -> " + nearestPalindrome(num));
        }
    }
}

99 -> 101
123 -> 121
1 -> 0
10 -> 9
12932 -> 12921
100 -> 99
999999999999999 -> 1000000000000001

Time: O(d). Space: O(d).

A mirrored prefix - 1 or prefix + 1 can have the wrong length (for "10", prefix 1 - 1 = 0 mirrors to 0), but such a value is never closer than candidates 4 and 5, so it's harmless to include. best starts at -1, which no candidate can equal because every candidate is at least 0.

Edge cases

• Single digit: "1" gives "0", and "0" isn't a valid input because it's not positive.
• Already a palindrome: num itself is excluded, so "121" gives "111" (131 is equally close, and 111 is smaller).
• All nines and powers of ten switch length: "999" gives "1001", and "1000" gives "999".