# Perl Weekly Challenge 114: Next Palindrome Number

by Abigail ## Challenge

You are given a positive integer $N. Write a script to find out the next Palindrome Number higher than the given integer $N.

### Example

Input: $N = 1234 Output: 1331 Input:$N = 999
Output: 1001


## Discussion

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:

• If $$|N|$$ is even, then $$P(N) = N^{f'}\overline{N^{f'}}$$.
• Else, if $$d_{k+1} = 9$$, then $$P(N) = N^{f'}0\overline{N^{f'}}$$.
• Otherwise, $$P(N) = N^f(d_{k+1}+1)\overline{N^{f}}$$.

## Solutions

### Perl

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.