Sponsored
Sponsored
This approach involves mirroring the first half of the number to form the second half which can create a potential palindrome. After forming the basic mirrored palindrome, consider the numbers formed by adjusting the half upwards and downwards. This will cover all possible close numbers. Finally, choose the closest and smallest palindrome by comparing all options.
Time Complexity: O(n) where n is the length of the string, as it involves mirroring which is a linear operation.
Space Complexity: O(n) for storing temporary palindrome strings.
1#include <iostream>
2#include <string>
3#include <cmath>
4#include <climits>
5using namespace std;
6
7long long mirrorPalindrome(string str) {
8 int n = str.size();
9 for (int i = 0; i < n / 2; ++i) {
10 str[n - 1 - i] = str[i];
11 }
12 return stoll(str);
13}
14
15string closestPalindrome(string n) {
16 int len = n.size();
17 long long original = stoll(n);
18 long long best = LLONG_MAX;
19 string result;
20
21 // Generate basic, lower and higher mirroring
22 string lower = n, higher = n;
23
24 long long mirrorValue = mirrorPalindrome(n);
25
26 // Compare different mirroring options
27 if (mirrorValue != original) best = mirrorValue;
28
29 lower[(len-1)/2] = lower[(len-1)/2] == '0' ? '9' : lower[(len-1)/2] - 1;
30 long long lowMirror = mirrorPalindrome(lower);
31 if (abs(lowMirror - original) < abs(best - original) || (abs(lowMirror - original) == abs(best - original) && lowMirror < best)) {
32 best = lowMirror;
33 }
34
35 higher[(len-1)/2] = '0' + (higher[(len-1)/2] - '0' + 1) % 10;
36 long long highMirror = mirrorPalindrome(higher);
37 if (abs(highMirror - original) < abs(best - original) || (abs(highMirror - original) == abs(best - original) && highMirror < best)) {
38 best = highMirror;
39 }
40
41 result = to_string(best);
42 return result;
43}The C++ solution uses string operations to handle number adjustments and convert versions of the number into potential palindromes. By modifying the significant digits, it creates candidate palindromes and selects the best match based on the smallest distance from the original number.