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.
1def mirror_palindrome(s):
2 return int(s[:len(s)//2] + s[:(len(s)+1)//2][::-1])
3
4
5def closest_palindrome(n):
6 length = len(n)
7 original = int(n)
8 best = float('inf')
9
10 mirror_value = mirror_palindrome(n)
11
12 candidates = {mirror_value}
13 center = (length - 1) // 2
14
15 lower = list(n)
16 lower[center] = chr(ord(lower[center]) - 1)
17 candidates.add(mirror_palindrome(''.join(lower)))
18
19 higher = list(n)
20 higher[center] = chr(ord(higher[center]) + 1)
21 candidates.add(mirror_palindrome(''.join(higher)))
22
23 for c in candidates:
24 if c != original:
25 if abs(c - original) < abs(best - original) or (abs(c - original) == abs(best - original) and c < best):
26 best = c
27
28 return str(best)The Python solution uses slicing and string reversal to quickly generate mirrored candidates. It loops through potential candidates and updates based on distance criteria, efficiently generating options through array manipulation and comparisons.