leetcode

commit a71264394dc0c6e18c40fc5498a9869c11d8a904
parent 8f24c825bc456233bcbee864de5798831afb5c95
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 24 Aug 2024 11:01:21 +0200

Daily Problem

Diffstat:
A
Problems/0564.cpp
 | 
41
+++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 42 insertions(+), 0 deletions(-)
diff --git a/Problems/0564.cpp b/Problems/0564.cpp
@@ -0,0 +1,41 @@
+class Solution {
+    long long generate(long long left, bool isEvenn) const {
+        long long palindrome = left;
+        if (!isEvenn) left /= 10;
+        while (left > 0) {
+            palindrome = palindrome * 10 + left % 10;
+            left /= 10;
+        }
+        return palindrome;
+    }
+
+  public:
+    string nearestPalindromic(const string &s) const {
+        if (s == "999999999999999999") return "1000000000000000001";
+
+        const long long number = stoll(s);
+        if (number <= 10) return to_string(number - 1);
+        if (number == 11) return "9";
+
+        const int n = size(s);
+        const long long left = stoll(s.substr(0, (n + 1) / 2));
+
+        long long vec[5] = {generate(left - 1, n % 2 == 0), generate(left, n % 2 == 0),
+                            (long long)pow(10, n - 1) - 1, (long long)pow(10, n) + 1,
+                            left < 999999999 ? generate(left + 1, n % 2 == 0)
+                                             : stoll("1" + string(n - 1, '0') + "1")};
+
+        long long res = 0, mini = LLONG_MAX;
+        for (const auto crnt : vec) {
+            if (crnt == number) continue;
+
+            const auto diff = abs(crnt - number);
+            if (diff < mini || (diff == mini && crnt < res)) {
+                mini = diff;
+                res = crnt;
+            }
+        }
+
+        return to_string(res);
+    }
+};
diff --git a/README.md b/README.md
@@ -399,6 +399,7 @@ for solving problems.
 |  0560  |   Medium   | [Subarray Sum Equals K](Problems/0560.cpp)                                                         |
 |  0561  |    Easy    | [Array Partition](Problems/0561.cpp)                                                               |
 |  0563  |    Easy    | [Binary Tree Tilt](Problems/0563.cpp)                                                              |
+|  0564  |    Hard    | [Find the Closest Palindrome](Problems/0564.cpp)                                                   |
 |  0565  |   Medium   | [Array Nesting](Problems/0565.cpp)                                                                 |
 |  0566  |    Easy    | [Reshape the Matrix](Problems/0566.cpp)                                                            |
 |  0567  |   Medium   | [Permutation in String](Problems/0567.cpp)                                                         |