The Next Palindrome

May 22, 2009

This exercise comes originally from the Sphere Online Judge; I read it on Proggit based on a blog posting by Chethan T. So many of the answers were wrong that I decided it would make a good exercise for Programming Praxis. Here is SPOJ’s statement of the exercise:

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Your task is to write a function that calculates the next palindrome larger than its input. When you are finished, you are welcome to read or run a suggested solution, or post your own solution or discuss the exercise in the comments below.

Pages: 1 2

18 Responses to “The Next Palindrome”

1. Jaime Vargas said

;; It doesn’t need to be that complicated.
;; Below is a simpler solution

(define (next-palindrome n)
(define (next-palindrome* n)
(define digits-of-n (string->list (format “~a” n)))
(cond
[(equal? digits-of-n (reverse digits-of-n)) n]
[else (next-palindrome* (add1 n))]))
(next-palindrome* (add1 n)))

(map next-palindrome ‘(0 88 808 1999 2133 9999 99999)) ==> ‘(1 99 818 2002 2222 10001 100001)

2. lilac said

Here’s how I did it:

bisect xs = go xs xs where
go xs [] = ([],[],xs)
go (x:xs) (_:[]) = ([],[x],xs)
go (x:xs) (_:_:ys) = let (fs,m,ss) = go xs ys in (x:fs,m,ss)

increment = foldr go ([],True) where
go ‘9’ (xs,True) = (‘0′:xs,True)
go x (xs,True) = (succ x:xs,False)
go x (xs,False) = (x:xs,False)

nextPalindrome xs | fhr > secondHalf = firstHalf ++ middle ++ fhr
| otherwise = startInc ++ endInc where
(firstHalf, middle, secondHalf) = bisect xs
fhr = reverse firstHalf
(incremented, carry) = increment (firstHalf ++ middle)
incremented’ | carry = ‘1’:incremented
| otherwise = incremented
startInc | carry = init incremented’
| otherwise = incremented’
endInc | null middle = reverse incremented’
| otherwise = tail (reverse incremented’)

It’s a bit fiddly, but there’s only really two cases: first half reversed > second half: take the palindrome starting with the first half. first half reversed <= second half: take the palindrome starting with the first half plus one (being careful to drop a digit if we increase the length in so doing).

3. Jaime Vargas said

;; Hopefully. Better formated

```(define (next-palindrome n)
(define (next-palindrome* n)
(define digits-of-n (string->list (format "~a" n)))
(cond
[(equal? digits-of-n (reverse digits-of-n)) n]
[else (next-palindrome* (add1 n))]))
(next-palindrome* (add1 n)))
```
4. lilac said

@Jaime Vargas: note the problem requires this to work on inputs 1000000 digits. Try your program on (10^500000 – 1) * (10^500000).

5. lilac said

Once more with formatting?

```bisect xs = go xs xs where
go xs [] = ([],[],xs)
go (x:xs) (_:[]) = ([],[x],xs)
go (x:xs) (_:_:ys) = let (fs,m,ss) = go xs ys in (x:fs,m,ss)

increment = foldr go ([],True) where
go '9' (xs,True) = ('0':xs,True)
go x   (xs,True) = (succ x:xs,False)
go x   (xs,False) = (x:xs,False)

nextPalindrome xs | fhr > secondHalf = firstHalf ++ middle ++ fhr
| otherwise        = startInc ++ endInc where
(firstHalf, middle, secondHalf) = bisect xs
fhr = reverse firstHalf
(incremented, carry) = increment (firstHalf ++ middle)
incremented' | carry = '1':incremented
| otherwise = incremented
startInc | carry     = init incremented'
| otherwise = incremented'
endInc | null middle = reverse incremented'
| otherwise   = tail (reverse incremented')```
6. […] Praxis – The Next Palindrome By Remco Niemeijer Today’s Programming Praxis problem is about palindromic numbers, i.e. numbers that read the same backwards […]

7. Remco Niemeijer said

My Haskell solution (see http://bonsaicode.wordpress.com/2009/05/22/programming-praxis-%E2%80%93-the-next-palindrome/ for a version with comments):

```nextPalindrome :: Integer -> String
nextPalindrome n =
half ++ drop (mod (length . show \$ n + 1) 2) (reverse half)
where l = length . show \$ n
half = take (div l 2 + 1) . show \$ div n (10 ^ div l 2) + 1

main :: IO ()
main = do
print \$ map nextPalindrome [0, 88, 808, 1999, 2133, 9999, 99999]
print \$ (takeWhile (<= 10^5) \$ iterate (read . nextPalindrome) 0)
== filter (\x -> show x == reverse (show x)) [0..10^5]
```
8. Jaime Vargas said

Lilac, my solution still applies eventhough it is inneficient.

9. Remco Niemeijer said

Updated version that’s one line shorter and 50% faster:

```nextPalindrome :: Integer -> String
nextPalindrome n = half ++ drop (mod l 2) (reverse half)
where l    = length . show \$ n + 1
half = take (div l 2 + 1) . show \$ div n (10 ^ div l 2) + 1
```
10. programmingpraxis said

Remco, please try nextPalindrome 9919.

11. Jaime Vargas said

;; Take 2: Efficient version

```(define (n->list n)
(map (λ (x) (- (char->integer x) 48)) (string->list (format "~a" n))))

(define (list->n l)
(foldl (λ (x a) (+ (* 10 a) x)) 0 l))

(define (scale-of n)
(string-length (format "~a" n)))

(define (make-palindromes n)
(define digits (n->list n))
(list (list->n (append digits (reverse digits)))
(list->n (append digits (rest (reverse digits))))))

(define (palindrome? n)
(let ([digits (n->list n)])
(equal? digits (reverse digits))))

(define (next-palindrome n)
(define-values (q r) (quotient/remainder n (expt 10 (quotient (scale-of n) 2))))
(define candidates (cons (add1 n)
(append (make-palindromes q)
(make-palindromes (add1 q))
(make-palindromes (quotient (add1 q) 10)))))
(apply min (filter (λ (x) (and (> x n) (palindrome? x))) candidates)))
```
12. Remco Niemeijer said

New version that works correctly for 9919:

```import Data.List.Split

nextPalindrome :: Integer -> String
nextPalindrome n = palindrome r where
l = length . show \$ n + 1
[s, m] = splitPlaces [div (l - 1) 2, 2 - mod l 2] \$ show n
palindrome x = x ++ drop (mod l 2) (reverse x)
r = if head m > last m then s ++ [head m]
else take (div (l + 1) 2) . show \$ div n (10 ^ div l 2) + 1

main :: IO ()
main = do
print \$ map nextPalindrome [0, 88, 808, 1999, 2133, 9999, 99999]
print \$ (takeWhile (<= 10^6) \$ iterate (read . nextPalindrome) 0)
== filter (\x -> show x == reverse (show x)) [0..10^6]
```
13. programmingpraxis said

Remco,

I’m curious. In the first version, how did 9919, or any of the smaller numbers where the second half is less than the first half, pass your test? The test looks to me like it should have worked.

14. FalconNL said

They didn’t, because there was no such test. In the 0, 88…99999 list you used the second half is always greater than or equal to the first half.
The other test just recursively calls nextPalindrome, so the input number is always symmetrical, in which case my original algorithm works ok.
Since there was no test for that type of case I never noticed that bug.

15. lilac said

@Jaime Vargas: If thermodynamics means it’s impossible for your program to be executed on certain valid inputs (because any computing device would break down due to entropy first), then I would say the solution does not apply. 10^499978 years is plenty of time for that (and that’s assuming an insanely fast computer is used).

16. Chethan T said

Hey I am Happy To see this Post
“Next Palindrome Number”! which was posted on my blog!
And Thanks For Solving This!
Very Nice Collection!

17. RandomC# said

This is a solution in c#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeapYear_Trial
{
class Program
{
public bool Palindrome(string number)
{
return number.SequenceEqual(number.Reverse());

}
static void Main(string[] args)
{
Program obj = new Program();

Console.WriteLine(“Input a number “);
int num = Convert.ToInt32(Console.ReadLine());

int nextNum = num + 1;
while(!obj.Palindrome(nextNum.ToString()))
{
nextNum += 1;
}

Console.WriteLine(“The next smallest palindrome larger than {0} is {1}”, num, nextNum);
}
}
}