smallest number greater than given number which is a palindrome

Question

This was asked in an interview. Given a number, say 900, output the smallest palindrome greater than the number, 909 in this case. I gave a brute force solution that checks every number but I'm assuming there's a better way to go about this

Answer 1

Copy the first digit to the last, second digit to the second-last etc until you reach the center digit (or center 2 digits if there is an even number of digits).

If the resulting number is smaller than the original number, increase the center digit/center 2 digits by one. If they are 9, set them to zero and retry with the 2 digits next to them, moving outwards until you hit a non-9.

Edit:

If the loop that moves outwards never hits a non-9, prepend a 1 to the string, set all digits except the last one to 0, and the last one to 1. This is the same as adding 2 to the number.

Answer 2

Just for fun, here's a simple implementation in Python (using essentially the same algorithm as described by Guntram Blohm).

def next_palindrome(n):
    """
    Given a non-negative integer n, return the first integer strictly
    greater than n whose decimal representation is palindromic.

    """
    s = str(n + 1)
    l = len(s)
    if s[:l//2][::-1] < s[(l+1)//2:]:
        head = str(int(s[:(l+1)//2])+1)
    else:
        head = s[:(l+1)//2]
    return int(head + head[:l//2][::-1])

And some sample output:

>>> next_palindrome(123)
131
>>> next_palindrome(4321)
4334
>>> next_palindrome(999)
1001

Answer 3

Though what has been answered above is absolutely correct. Just to add more understanding :)

There can be three different types of inputs that need to be handled separately.

1) The input number is palindrome and has all 9s. For example “9 9 9″. Output should be “1 0 0 1″

2) The input number is not palindrome. For example “1 2 3 4″. Output should be “1 3 3 1″

3) The input number is palindrome and doesn’t have all 9s. For example “1 2 2 1″. Output should be “1 3 3 1″.

Solution for input type 1 is easy. The output contains n + 1 digits where the corner digits are 1, and all digits between corner digits are 0.

Now let us first talk about input type 2 and 3. Let us first define the following two terms:

Left Side: The left half of given number. Left side of “1 2 3 4 5 6″ is “1 2 3″ and left side of “1 2 3 4 5″ is “1 2″

Right Side: The right half of given number. Right side of “1 2 3 4 5 6″ is “4 5 6″ and right side of “1 2 3 4 5″ is “4 5″ To convert to palindrome, we can either take the mirror of its left side or take mirror of its right side. However, if we take the mirror of the right side, then the palindrome so formed is not guaranteed to be next larger palindrome.

So, we must take the mirror of left side and copy it to right side. But there are some cases that must be handled in different ways. See the following steps.

We will start with two indices i and j. i pointing to the two middle elements (or pointing to two elements around the middle element in case of n being odd). We one by one move i and j away from each other.

Step 1. Initially, ignore the part of left side which is same as the corresponding part of right side. For example, if the number is “8 3 4 2 2 4 6 9″, we ignore the middle four elements. i now points to element 3 and j now points to element 6.

Step 2. After step 1, following cases arise:

Case 1: Indices i & j cross the boundary. This case occurs when the input number is palindrome. In this case, we just add 1 to the middle digit (or digits in case n is even) propagate the carry towards MSB digit of left side and simultaneously copy mirror of the left side to the right side. For example, if the given number is “1 2 9 2 1″, we increment 9 to 10 and propagate the carry. So the number becomes “1 3 0 3 1″

Case 2: There are digits left between left side and right side which are not same. So, we just mirror the left side to the right side & try to minimize the number formed to guarantee the next smallest palindrome. In this case, there can be two sub-cases.

2.1) Copying the left side to the right side is sufficient, we don’t need to increment any digits and the result is just mirror of left side. Following are some examples of this sub-case. Next palindrome for “7 8 3 3 2 2″ is “7 8 3 3 8 7″ Next palindrome for “1 2 5 3 2 2″ is “1 2 5 5 2 1″ Next palindrome for “1 4 5 8 7 6 7 8 3 2 2″ is “1 4 5 8 7 6 7 8 5 4 1″ How do we check for this sub-case? All we need to check is the digit just after the ignored part in step 1. This digit is highlighted in above examples. If this digit is greater than the corresponding digit in right side digit, then copying the left side to the right side is sufficient and we don’t need to do anything else.

2.2) Copying the left side to the right side is NOT sufficient. This happens when the above defined digit of left side is smaller. Following are some examples of this case. Next palindrome for “7 1 3 3 2 2″ is “7 1 4 4 1 7″ Next palindrome for “1 2 3 4 6 2 8″ is “1 2 3 5 3 2 1″ Next palindrome for “9 4 1 8 7 9 7 8 3 2 2″ is “9 4 1 8 8 0 8 8 1 4 9″ We handle this subcase like Case 1. We just add 1 to the middle digit (or digits in ase n is even) propagate the carry towards MSB digit of left side and simultaneously copy mirror of the left side to the right side.

SOURCE: http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/