Task 1: Closest Palindrome
You are given a string, $str, representing an integer.
Write a script to find the closest palindrome integer to the given integer string, excluding the integer itself. If there are multiple palindromes with the same minimal absolute difference, return the smallest one.
Method Explanation
Finding the closest palindrome to a number string $S$ without scanning all numbers sequentially requires analyzing how palindromes are formed around their center. A palindrome is completely determined by its first half (including the middle element if the length is odd).
To generate candidate palindromes that could be closest to $S$:
- Extract the prefix consisting of the first $\lceil \text{length} / 2 \rceil$ digits.
- Consider three primary variations: prefix $- 1$, prefix $+ 0$, and prefix $+ 1$. Reflect each variation to form a full palindrome of the same length.
- Handle boundary/edge cases where the number of digits changes:
- Underflow edge case: A sequence of nines with length $\text{length} - 1$ (e.g., $1000 \to 999$).
- Overflow edge case: A number of the form $10\dots01$ with length $\text{length} + 1$ (e.g., $999 \to 1001$).
- Filter out the original number itself (as required by the task).
- Select the candidate with the minimum absolute difference from the target number. In the event of a tie in difference, choose the numerically smaller palindrome.
Perl Solution
#!/usr/bin/env perl
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);
use Test::More;
signature_for closest_palindrome => (
method => 0,
positional => [ Str ],
);
sub closest_palindrome ($n_str) {
my $n = int($n_str);
my $len = length($n_str);
my $is_even = $len % 2 == 0;
my $mid = int($len / 2);
# Obtain the left part of the number
my $left_len = $is_even ? $mid : $mid + 1;
my $left = substr($n_str, 0, $left_len);
my @candidates;
for my $i (-1, 0, 1) {
my $new_left = int($left) + $i;
next if $new_left < 0;
my $new_left_str = "$new_left";
my $palindrome;
if ($is_even) {
$palindrome = $new_left_str . reverse($new_left_str);
} else {
$palindrome = $new_left_str . reverse(substr($new_left_str, 0, -1));
}
push @candidates, $palindrome;
}
# Edge cases (e.g. 99 -> 101, 100 -> 99)
push @candidates, ('9' x ($len - 1)) if $len > 1;
push @candidates, '1' . ('0' x ($len - 1)) . '1';
# Remove the original number from candidates
@candidates = grep { $_ ne $n_str } @candidates;
# Find the closest palindrome
my $min_diff = undef;
my $closest_palindrome = undef;
for my $candidate (@candidates) {
my $diff = abs(int($candidate) - $n);
if (!defined $min_diff || $diff < $min_diff || ($diff == $min_diff && int($candidate) < int($closest_palindrome))) {
$min_diff = $diff;
$closest_palindrome = $candidate;
}
}
return $closest_palindrome;
}
Python Solution
from __future__ import annotations
from collections.abc import Sequence
def closest_palindrome(n_str: str) -> str:
"""Find the closest palindrome integer string to n_str, excluding itself."""
n = int(n_str)
length = len(n_str)
is_even = length % 2 == 0
mid = length // 2
left_len = mid if is_even else mid + 1
left = n_str[:left_len]
candidates: set[str] = set()
for diff in (-1, 0, 1):
new_left = str(int(left) + diff)
if len(new_left) != left_len and diff != 0:
continue
if is_even:
pal = new_left + new_left[::-1]
else:
pal = new_left + new_left[:-1][::-1]
candidates.add(pal)
# Edge cases (e.g. 100 -> 99, 99 -> 101)
if length > 1:
candidates.add("9" * (length - 1))
candidates.add("1" + ("0" * (length - 1)) + "1")
candidates.discard(n_str)
min_diff: int | None = None
closest_pal = ""
for cand in sorted(candidates, key=lambda x: (abs(int(x) - n), int(x))):
if not cand:
continue
diff = abs(int(cand) - n)
if diff == 0:
continue
if min_diff is None or diff < min_diff:
min_diff = diff
closest_pal = cand
return closest_pal