Problem

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.

Examples

Example 1:

1
2

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

Example 2:

1
2
3

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

Solution

Method 1 - Compare 5 Candidates

Logic

nearestPalindromic Method
  • This method serves as the main logic.
  • It converts the input string n to a long integer num.
  • It calls getCandidates to generate all potential palindrome candidates.
  • It iterates through all candidates to find the closest palindrome by comparing the absolute differences.
  • It ensures the chosen palindrome is not the original number itself.
  • It returns the closest palindrome in string format.

getCandidates Method

We can write getCandidates function to get the candidates for palindrome.

This method generates all plausible palindrome candidates.

  • It first adds edge cases:
    • All 9s of one less digit (e.g., 999 -> 99)
    • 1 followed by zeros followed by 1 (e.g., 999 -> 1001)
  • It then constructs palindromes using the prefix of the original number:
    • Takes the first half (plus middle digit if odd length).
    • Creates palindromes by decrementing, keeping, and incrementing this prefix, mirroring it appropriately for odd and even lengths.
  • These palindromes are added to a list and returned.

Cases of Palindromes

  1. Case 1: Largest Number with One Less Digit:
    • This is the largest number that can be formed with one less digit than the input number.
    • For example, for input 99, this would be 9.
  2. Case 2: Smallest Number with One More Digit:
    • This is the smallest number that can be formed with one more digit than the input number.
    • For example, for input 99, this would be 101.
  3. Case 3-5: Mirroring the Prefix with Adjustments:
    • These cases involve forming palindromic numbers by taking the prefix (first half) of the input number, then adjusting this prefix by -1, 0, and +1, and mirroring it to form full palindromes.
    • For example, for input 123:
      • Original Prefix (Adjusted by 0):
        • Prefix 12: Mirror to get 121.
      • Prefix Adjusted by +1:
        • Prefix 13: Mirror to get 131.
      • Prefix Adjusted by -1:
        • Prefix 11: Mirror to get 111.

The total number of palindrome cases we handle in this solution can therefore be summarized as:

  1. All 9s (largest number with one less digit).
  2. 1 followed by zeros and ending in 1 (smallest number with one more digit).
  3. Mirrored prefixes:
    • Original prefix.
    • Prefix + 1.
    • Prefix - 1.

This results in a total of 5 cases to consider for checking the nearest palindrome.

Summary
  1. All 9s (Largest Number with One Less Digit):
    • Example: 99 -> 9
  2. 1 followed by zeros and ending in 1 (Smallest Number with One More Digit):
    • Example: 99 -> 101
  3. Mirror of the Prefix (Original, -1, +1):
    • Example: 123 results in the following palindromes:
      • Original Prefix: 121
      • Prefix +1: 131
      • Prefix -1: 111

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public class Solution {
    public String nearestPalindromic(String n) {
        long num = Long.parseLong(n);
        List<Long> candidates = getCandidates(n);

        long closest = -1;
        for (long candidate : candidates) {
            if (candidate != num) {
                if (closest == -1
                    || Math.abs(candidate - num) < Math.abs(closest - num)
                    || (Math.abs(candidate - num) == Math.abs(closest - num)
                        && candidate < closest)) {
                    closest = candidate;
                }
            }
        }

        return String.valueOf(closest);
    }

    private List<Long> getCandidates(String n) {
        int len = n.length();
        List<Long> candidates = new ArrayList<>();

        // Case 1: Largest number with one less digit (all 9s)
        candidates.add((long) Math.pow(10, len - 1) - 1);

        // Case 2: Smallest number with one more digit (100...001)
        candidates.add((long) Math.pow(10, len) + 1);

        long prefix = Long.parseLong(n.substring(0, (len + 1) / 2));

        for (int i = -1; i <= 1; i++) {
            String newPrefix = String.valueOf(prefix + i);
            String candidate;
            if (len % 2 == 0) {
                candidate = newPrefix
                    + new StringBuilder(newPrefix).reverse().toString();
            } else {
                candidate = newPrefix
                    + new StringBuilder(newPrefix).reverse().substring(1);
            }
            candidates.add(Long.parseLong(candidate));
        }

        return candidates;
    }
}

Complexity

  • ⏰ Time complexity: O(len(n)) where len is the length of input text
  • 🧺 Space complexity: O(1) as we are not using extra space