diff options
-rw-r--r-- | find_closest_palindrome.c | 68 | ||||
-rw-r--r-- | find_closest_palindrome.py | 53 |
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")) |