aboutsummaryrefslogtreecommitdiff
path: root/find_closest_palindrome.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-24 02:28:06 -0600
committerJack Sangdahl <[email protected]>2024-08-24 02:28:06 -0600
commit3e70e160aa6c76fbd37b4e0be2479c0db09a849b (patch)
treefdb90b7adede5d3197141fc3358ea41cea646e8c /find_closest_palindrome.py
parent9ec4c81450f3fb9429db5bac26d8400e4b8264d6 (diff)
downloadleetcode-3e70e160aa6c76fbd37b4e0be2479c0db09a849b.tar.gz
leetcode-3e70e160aa6c76fbd37b4e0be2479c0db09a849b.zip
564. find the closest palindrome
Diffstat (limited to 'find_closest_palindrome.py')
-rw-r--r--find_closest_palindrome.py53
1 files changed, 53 insertions, 0 deletions
diff --git a/find_closest_palindrome.py b/find_closest_palindrome.py
new file mode 100644
index 0000000..12f44fe
--- /dev/null
+++ b/find_closest_palindrome.py
@@ -0,0 +1,53 @@
+# 564. Find the Closest Palindrome
+
+"""
+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 minimised
+between two integers.
+"""
+
+
+class Solution(object):
+ def nearestPalindromic(self, n):
+ """
+ :type n: str
+ :rtype: str
+ """
+ if int(n) <= 10 or (int(n) % 10 == 0 and int(n[1:]) == 0):
+ return str(int(n) - 1)
+ elif int(n) == 11 or (int(n) % 10 == 1 and n[0] == "1" and int(n[1:-1]) == 0):
+ return str(int(n) - 2)
+ elif n[0] == "9" and n[0] * len(n) == n:
+ return str(int(n) + 2)
+ else:
+
+ def get_panindrome(base, is_even_length=True):
+ if is_even_length:
+ return base + "".join(reversed(base))
+ else:
+ return base[:-1] + base[-1] + "".join(reversed(base[:-1]))
+
+ even_size = len(n) % 2 == 0
+ palindrome_base = (
+ int(n[0 : len(n) // 2]) if even_size else int(n[0 : len(n) // 2 + 1])
+ )
+ is_n_palindrome = get_panindrome(str(palindrome_base), even_size) == n
+ base_candidates = (
+ [palindrome_base - 1, palindrome_base + 1]
+ if is_n_palindrome
+ else [palindrome_base - 1, palindrome_base, palindrome_base + 1]
+ )
+ diff = float("inf")
+ for base_candidate in base_candidates:
+ candidate = int(get_panindrome(str(base_candidate), even_size))
+ if abs(candidate - int(n)) < diff:
+ diff = abs(candidate - int(n))
+ min_base_candidate = str(base_candidate)
+ return get_panindrome(min_base_candidate, even_size)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.nearestPalindromic("123"))
+ print(obj.nearestPalindromic("1"))