You are given a positive integer
$N.Write a script to find out the next Palindrome Number higher than the given integer
$N.
Input: $N = 1234 Output: 1331 Input: $N = 999 Output: 1001
A naive way of solving this problem would be to start counting from \(N\), and checking each number to see if it's a palindrome. That will work well with tiny numbers, but it is very inefficient for numbers like \(99999999999990000000000000\). We can do better.
Let \(N\) be our input number, and \(P(N)\) the next palidrome higher than \(N\). Let \(|x|\) be the number of digits in the number \(x\). Let \(\overline{x}\) be the number we get when reversing the digits of \(x\).
We will first consider two special cases, before discussing the general case.
If \(N\) consists of all \(9\)s, then \(P(N) = N + 2\), which is a number which begins with a \(1\), ends with a \(1\), and has nothing but \(0\)s in between. \(|P(N)| = |x| + 1\). Note that this is the only case where \(|P(N)| \neq |N|\). In all other cases there is at least one palindrome greater than \(N\) with the same amount of numbers: all \(9\)s.
If \(N\) is a single digit number other than \(9\), then \(P(N) = N + 1\). Since in this case, \(N + 1\) is a single digit number, this obviously is a palindrome.
Otherwise, let \(N\) be \(d_{2k}d_{2k-1}...d_{k+1}d_{k}...d_{2}d_{1}\) (if \(|N|\) is even), or \(d_{2k+1}d_{2k}...d_{k+2}d_{k+1}d_{k}...d_{2}d_{1}\) (if \(|N|\) is odd).
Now, let \(N^f\) be the number which consists of the first \(k\) digits of \(N\), and \(N^l\) be the number which consists of the last \(k\) digits of \(N\). So, if \(|N|\) is even, \(N = N^fN^l\), and \(N = N^fd_{k+1}N^l\) if \(|N|\) is odd.
If \(\overline{N^f} > N^l\), then \(P(N) = N^f\overline{N^f}\) or \(P(N) = N^fd_{k+1}\overline{N^f}\). It should be obvious that \(P(N)\) is a palindrome, and greater than \(N\). It's also not hard to see there is no other palidrome \(p\) such that \(N < p < P(N)\).
If \(\overline{N^f} \leq N^l\), we cannot simply reverse the first part of \(N\). We would have to incremeant \(N^f\) or \(d_{k+1}\). Let \(N^{f'} = N^f + 1\). We now have three cases:
First the special cases (we have the input number in $_:
if (/^9+$/) {
say $_ + 2;
exit;
}
if (length ($_) == 1) {
say $_ + 1;
exit;
}
Otherwise, we split the number into three parts, where the middle part is zero or one digit, and the first and third part of equal length:
my $part1 = substr $_, 0, int length ($_) / 2;
my $part2 = substr $_, int length ($_) / 2, length ($_) % 2;
my $part3 = substr $_, int length ($_) / 2 + length ($_) % 2;
We can now compare the first and third part, add one if necessary, reverse the first part and print the result:
if (reverse ($part1) <= $part3) {
$part1 = "$part1$part2" + 1;
$part2 = chop $part1 if length $part2;
}
say $part1, $part2, scalar reverse ($part1);
Find the full program on GitHub.