aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_closest_palindrome.c68
-rw-r--r--find_closest_palindrome.py53
2 files changed, 121 insertions, 0 deletions
diff --git a/find_closest_palindrome.c b/find_closest_palindrome.c
new file mode 100644
index 0000000..51ad27d
--- /dev/null
+++ b/find_closest_palindrome.c
@@ -0,0 +1,68 @@
+// 564. Find the Closest Palindrome
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+static inline void substr(char *str, char *sub, int start, int size) {
+ memcpy(sub, &str[start], size);
+ sub[size] = '\0';
+}
+
+static long get_palindrome(long prefix, bool even_size) {
+ long long res = prefix;
+ if (!even_size)
+ prefix /= 10;
+ while (prefix) {
+ res = res * 10 + prefix % 10;
+ prefix /= 10;
+ }
+ return res;
+}
+
+char *nearestPalindromic(char *n) {
+ int len = strlen(n);
+ if (len == 1) {
+ n[0] = (((n[0] - '0') - 1) + '0');
+ return n;
+ }
+ char *ans = (char *)malloc((len + 3) * sizeof(char));
+ bool even_size = len % 2 ? false : true;
+ int prefix_size = even_size ? len / 2 - 1 : len / 2;
+ char *prefix_sub = (char *)malloc((prefix_size + 2) * sizeof(char));
+ substr(n, prefix_sub, 0, prefix_size + 1);
+ char *n_end;
+ long long prefix = strtoll(prefix_sub, &n_end, 10);
+ long long combinations[5] = {0};
+ combinations[0] = get_palindrome(prefix, even_size);
+ combinations[1] = get_palindrome(prefix - 1, even_size);
+ combinations[2] = get_palindrome(prefix + 1, even_size);
+ combinations[3] = (long long)(pow(10, len - 1) - 1);
+ combinations[4] = (long long)(pow(10, len) + 1);
+ long long diff = INT64_MAX, res = 0, orig_num = strtol(n, &n_end, 10);
+ for (int i = 0; i < 5; i++) {
+ long long curr = orig_num - combinations[i];
+ curr = abs((int)curr);
+ if (!curr)
+ continue;
+ else if (curr == diff && combinations[i] > res)
+ continue;
+ else if (fmin(curr, diff) == curr) {
+ res = combinations[i];
+ diff = curr;
+ }
+ }
+ sprintf(ans, "%lld", res);
+ free(prefix_sub);
+ return ans;
+}
+
+int main() {
+ char *n1 = "123", *n2 = "1";
+ printf("%s\n", nearestPalindromic(n1)); // expect: 121
+ printf("%s\n", nearestPalindromic(n2)); // expect: 0
+}
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"))