Skip to content

564. Find the Closest Palindrome 👎

  • Time:
  • Space:
 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) {
    const auto& [prevPalindrome, nextPalindrome] = getPalindromes(n);
    return abs(prevPalindrome - stol(n)) <= abs(nextPalindrome - stol(n))
               ? to_string(prevPalindrome)
               : to_string(nextPalindrome);
  }

 private:
  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 && (stol(prevHalf) + 1) % 10 == 0)
        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 {rbegin(s), rend(s)};
  }
};
 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
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]);
  }

  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 && (Long.parseLong(prevHalf) + 1) % 10 == 0)
        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
class Solution:
  def nearestPalindromic(self, n: str) -> str:
    def getPalindromes(s: str) -> tuple:
      num = int(s)
      k = len(s)
      palindromes = []
      half = s[0:(k + 1) // 2]
      reversedHalf = half[:k // 2][::-1]
      candidate = int(half + reversedHalf)

      if candidate < num:
        palindromes.append(candidate)
      else:
        prevHalf = str(int(half) - 1)
        reversedPrevHalf = prevHalf[:k // 2][::-1]
        if k % 2 == 0 and int(prevHalf) == 0:
          palindromes.append(9)
        elif k % 2 == 0 and (int(prevHalf) + 1) % 10 == 0:
          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[:k // 2][::-1]
        palindromes.append(int(nextHalf + reversedNextHalf))

      return palindromes

    prevPalindrome, nextPalindrome = getPalindromes(n)
    return str(prevPalindrome) if abs(prevPalindrome - int(n)) <= abs(nextPalindrome - int(n)) else str(nextPalindrome)