Skip to content

564. Find the Closest Palindrome 👎

  • Time: $O(\log n)$
  • Space: $O(\log n)$
 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
class Solution {
 public:
  string nearestPalindromic(string n) {
    const auto& [prevPalindrome, nextPalindrome] = getPalindromes(n);
    return abs(prevPalindrome - stol(n)) <= abs(nextPalindrome - stol(n))
               ? to_string(prevPalindrome)
               : to_string(nextPalindrome);
  }

 private:
  // Returns the two closest palindromes to the given number.
  pair<long, long> getPalindromes(const string& s) {
    const long num = stol(s);
    const int n = s.length();
    pair<long, long> palindromes;
    const string half = s.substr(0, (n + 1) / 2);
    const string reversedHalf = reversed(half.substr(0, n / 2));
    const long candidate = stol(half + reversedHalf);

    if (candidate < num)
      palindromes.first = candidate;
    else {
      const string prevHalf = to_string(stol(half) - 1);
      const string reversedPrevHalf = reversed(prevHalf.substr(0, n / 2));
      if (n % 2 == 0 && stol(prevHalf) == 0)
        palindromes.first = 9;
      else if (n % 2 == 0 && prevHalf == "9")
        palindromes.first = stol(prevHalf + '9' + reversedPrevHalf);
      else
        palindromes.first = stol(prevHalf + reversedPrevHalf);
    }

    if (candidate > num)
      palindromes.second = candidate;
    else {
      const string& nextHalf = to_string(stol(half) + 1);
      const string& reversedNextHalf = reversed(nextHalf.substr(0, n / 2));
      palindromes.second = stol(nextHalf + reversedNextHalf);
    }

    return palindromes;
  }

  string reversed(const string& s) {
    return {s.rbegin(), s.rend()};
  }
};

 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
class Solution {
  public String nearestPalindromic(String n) {
    final long[] palindromes = getPalindromes(n);
    return Math.abs(palindromes[0] - Long.parseLong(n)) <=
            Math.abs(palindromes[1] - Long.parseLong(n))
        ? String.valueOf(palindromes[0])
        : String.valueOf(palindromes[1]);
  }

  // Returns the two closest palindromes to the given number.
  private long[] getPalindromes(final String s) {
    final long num = Long.parseLong(s);
    final int n = s.length();
    long[] palindromes = new long[2];
    final String half = s.substring(0, (n + 1) / 2);
    final String reversedHalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString();
    final long candidate = Long.parseLong(half + reversedHalf);

    if (candidate < num)
      palindromes[0] = candidate;
    else {
      final String prevHalf = String.valueOf(Long.parseLong(half) - 1);
      final String reversedPrevHalf =
          new StringBuilder(prevHalf.substring(0, Math.min(prevHalf.length(), n / 2)))
              .reverse()
              .toString();
      if (n % 2 == 0 && Long.parseLong(prevHalf) == 0)
        palindromes[0] = 9;
      else if (n % 2 == 0 && prevHalf.equals("9"))
        palindromes[0] = Long.parseLong(prevHalf + '9' + reversedPrevHalf);
      else
        palindromes[0] = Long.parseLong(prevHalf + reversedPrevHalf);
    }

    if (candidate > num)
      palindromes[1] = candidate;
    else {
      final String nextHalf = String.valueOf(Long.parseLong(half) + 1);
      final String reversedNextHalf =
          new StringBuilder(nextHalf.substring(0, n / 2)).reverse().toString();
      palindromes[1] = Long.parseLong(nextHalf + reversedNextHalf);
    }

    return palindromes;
  }
}

 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
class Solution:
  def nearestPalindromic(self, n: str) -> str:
    prevPalindrome, nextPalindrome = self._getPalindromes(n)
    return (str(prevPalindrome)
            if abs(prevPalindrome - int(n)) <= abs(nextPalindrome - int(n))
            else str(nextPalindrome))

  def _getPalindromes(self, s: str) -> tuple[str, str]:
    """Returns the two closest palindromes to the given number."""
    num = int(s)
    sz = len(s)
    palindromes = []
    half = s[0:(sz + 1) // 2]
    reversedHalf = half[:sz // 2][::-1]
    candidate = int(half + reversedHalf)

    if candidate < num:
      palindromes.append(candidate)
    else:
      prevHalf = str(int(half) - 1)
      reversedPrevHalf = prevHalf[:sz // 2][::-1]
      if sz % 2 == 0 and int(prevHalf) == 0:
        palindromes.append(9)
      elif sz % 2 == 0 and prevHalf == '9':
        palindromes.append(int(prevHalf + '9' + reversedPrevHalf))
      else:
        palindromes.append(int(prevHalf + reversedPrevHalf))

    if candidate > num:
      palindromes.append(candidate)
    else:
      nextHalf = str(int(half) + 1)
      reversedNextHalf = nextHalf[:sz // 2][::-1]
      palindromes.append(int(nextHalf + reversedNextHalf))

    return palindromes