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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <limits.h>
5
6long long mirrorPalindrome(char *str) {
7 int n = strlen(str);
8 char result[n + 1];
9 strcpy(result, str);
10 for (int i = 0; i < n / 2; i++) {
11 result[n - 1 - i] = str[i];
12 }
13 return atoll(result);
14}
15
16char *closestPalindrome(char *n) {
17 int len = strlen(n);
18 long long original = atoll(n);
19 long long best = LLONG_MAX;
20 char *result = (char *)malloc(len + 2);
21
22 // Generate basic, lower and higher mirroring
23 char lower[len + 1], higher[len + 1];
24 strcpy(lower, n);
25 strcpy(higher, n);
26
27 long long mirrorValue = mirrorPalindrome(n);
28
29 // Compare different mirroring options
30 if (mirrorValue != original) best = mirrorValue;
31
32 lower[(len-1)/2]--; // Decrement the middle (or left middle)
33 long long lowMirror = mirrorPalindrome(lower);
34 if (abs(lowMirror - original) < abs(best - original) || (abs(lowMirror - original) == abs(best - original) && lowMirror < best)) {
35 best = lowMirror;
36 }
37
38 higher[(len-1)/2]++; // Increment the middle (or left middle)
39 long long highMirror = mirrorPalindrome(higher);
40 if (abs(highMirror - original) < abs(best - original) || (abs(highMirror - original) == abs(best - original) && highMirror < best)) {
41 best = highMirror;
42 }
43
44 sprintf(result, "%lld", best);
45 return result;
46}The C language solution creates a helper function to generate a mirrored palindrome given a string. It then creates potential palindrome candidates by mirroring the number, decrementing, and incrementing the middle digit(s). The closest candidate by absolute difference is selected as the solution.