Programming Interview Questions 19: Find Next Palindrome Number

Given a number, find the next smallest palindrome larger than the number. For example if the number is 125, next smallest palindrome is 131.

The naive algorithm is to increment the number until we get a palindrome. So at every iteration we check whether the new number is palindrome or not. This is the most straightforward non-optimal solution. The complexity depends on the number of digits in the number. If the number has 6 digits, we may have to increment it 999 times to get the smallest palindrome in the worst case (999000 to 999999). So the complexity is O(sqrt(N)), which is pretty bad. We can do it much better in O(logN) time, which is proportional to the number of digits in the given number.

There are two cases, whether the number of digits in the number is odd or even. We’ll start with analyzing the odd case. Let’s say the number is ABCDE, the smallest possible palindrome we can obtain from this number is ABCBA, which is formed by mirroring the number around its center from left to right (copying the left half onto the right in reverse order). This number is always a palindrome, but it may not be greater than the original number. If it is then we simply return the number, if not we increase the number. But which digit to increment? We don’t want to increment the digits on the left half because they increase the number substantially, and we’re looking for the smallest palindrome larger than the number. The digits on the right half increase the value of the number much less, but then to keep the number palindrome we’ll have to increment the digits on the left half as well, which will again result in a large increase. So, we increment the digit just in the middle by 1, which corresponds to adding 100 in this case. This way the number stays a palindrome, and the resulting number is always larger than the original number.

Here are some examples to clarify any doubt. Let’s say the given number is 250, we first take the mirror image around its center, resulting in 252. 252 is greater than 250 so this is the first palindrome greater than the given number, we’re done. Now let’s say the number is 123, now mirroring the number results in 121, which is less than the original number. So we increment it’s middle digit, resulting in 131. This is again the first smallest palindrome larger than the number. But what if the middle digit is 9 and mirroring the number results in a smaller value? Then simply incrementing the middle digit would not work. The solution is we first round up the number and then apply the procedure to it. For example if the number is 397, mirroring results in 393 which is less. So we round it up to 400 and solve the problem as if we got 400 in the first place. We take the mirror image, which is 404 and this is the result.

Now let’s analyze the case where the given number has even number of digits. Let’s say the given number is ABCD, similar to the odd case the smallest possible palindrome we can obtain from this number is ABBA (and yes their songs are awesome :). Again we did the mirror image around its center from left to right. But since the number has even number of digits the center now lies between 2nd (C, tenth digit) and 3rd (B, hundredth) digits (counting from right starting at 1). So let’s define the center digit as the middle two digits, 2nd and 3rd in our case. The strategy to find the next palindrome is same. First we mirror the number and check whether it’s greater than the given one. If it is then we return that number, if not we increment the middle two digits by 1, which means adding 110 in this case. Let’s again see some examples.

Assume the given number is 4512, we mirror the number around its center, resulting in 4554. This is greater than the given number so we’re done. Now let the number be 1234, mirroring results in 1221 which is less than the original number. So we increment the middle two digits, resulting in 1331 which is the result. What if the middle digits become 9 after mirroring and the resulting number is smaller than the original one? Then we again round up the number and solve the problem as if we got the round number in the first place. For example, if the given number is 1997 mirroring would give 1991, which is less. So we round it up to 2000 and solve as if it were the original number. We mirror it, resulting in 2002 and this is the result. The code will make everything clear:

def nextPalindrome(num):
    length=len(str(num))
    oddDigits=(length%2!=0)
    leftHalf=getLeftHalf(num)
    middle=getMiddle(num)
    if oddDigits:
        increment=pow(10, length/2)
        newNum=int(leftHalf+middle+leftHalf[::-1])
    else:
        increment=int(1.1*pow(10, length/2))
        newNum=int(leftHalf+leftHalf[::-1])
    if newNum>num:
        return newNum
    if middle!='9':
        return newNum+increment
    else:
        return nextPalindrome(roundUp(num))
 
def getLeftHalf(num):
    return str(num)[:len(str(num))/2]
 
def getMiddle(num):
    return str(num)[(len(str(num))-1)/2]
 
def roundUp(num):
    length=len(str(num))
    increment=pow(10,((length/2)+1))
    return ((num/increment)+1)*increment

The complexity of this algorithm is O(logN), because the complexity of mirroring is proportional to the number of digits in the number, which is the ceiling of logN. It’s optimal because we have to scan every digit of the number at least in the worst case. It’s also more efficient than the straightforward solution, because if the given number is a million we need in the order of 10 operations, instead of 1000 with the naive approach.

I personally like this question because it involves some simple math and creative thinking.

VN:F [1.9.22_1171]
Rating: 9.7/10 (36 votes cast)
Programming Interview Questions 19: Find Next Palindrome Number, 9.7 out of 10 based on 36 ratings

This entry was posted in Programming Interview. Bookmark the permalink.
  • Arda Antikacioglu

    Actually, this takes O(log(n)) time since mirroring takes as long as the length of n, which is still linear in the length of the input and can be proven to be optimal.

    • Arden

      Thanks for the notice Arda, updated the article.

  • Himanshu Sharma

    I first tried this question for hours but couldn’t bring down the cases to a manageable number. Your solution is simply beautiful. Thanx a lot

  • abhijit shingate

    Very Good Logic :-) Thankx :-)

  • rahul sharma

    I think u left 1 case when N=999, it should return 1001, instead ur algo returns 1009.
    Apart from it the logic u have used is kinda cool.

    • dennisbot

      I think 999 it’s already a palindrome :) , so GIGO applies here, btw we can add a pre scan verifying whether it’s already an palindrome or not.

      • MD

        the algorithm is right. 999, middle is 9 so we round up the number to 1000
        Then we mirror, 1000 becomes 1001, and 1001 is greater than 999
        so we return 1001

  • zoom

    Above would not work if number is 129913 since your algo would round off 129 to 130 and calculate 130031since 129921 is the right ans

    • dimkadimon

      The mirroring step will give you 129921 and this is where you finish. So the algorithm is correct.

  • src

    The complexity is not O(log N), where N is number of digits of the string. Remember input is a string, not the number. Complexity of this method is O(N), where as for the naive one it is O(10^N)

  • test

    did u test 1997, it gives you 2101 …

  • berry78

    fails for 1091. The roundUp function rounds it to 2000 whereas the next largest palindrome should be 1111.

    • Rohit

      round up fraction will give 1100 not 2000. This gives 1111

  • venky

    awsome explaination loved it :)

  • so_what

    well explanation with example thank alot and upload more algorithm with examples

  • so_what

    oh!! but still give time limit exceeded in spoj and codechef ,i have implemented it but tle
    helpp plzzz

  • Vikas

    What is the meaning of “newNum>num:”
    When i am trying to run. it is showing syntax error

  • kinshuk chandra

    Here is my basic algo:

    1. Break the number into 2 halfs “2133″ = “21″,”33″
    2. Now if first half is greater than 2nd half AND first half is same
    size as 2nd half AND reverse(first) is greater than 2nd half, then
    nextPalindrome = first + reverse(first), otherwise go to step 3.
    Example 783322 = 783 + 387 = 783387. However 2133 wont hold. Nor will
    1001, as first = 10, and last = 01 = 1
    3. Increment the first half by 1,
    first = first+1
    nextPalindrome = first + reverse(first)
    Example 2133, first = 21, first+1 = 22, Now concat first and reverse first = 2222
    Here is my post –
    http://k2code.blogspot.in/2014/05/finding-next-palindrome-for-given-number.html

  • learning

    hey! nice explanation of the logic.. can you add explanation on how you calculate the complexity figures in this particular solution?