Geek asks and answers

Smallest number is greater than a given number, which is a palindrome

This was asked in an interview. Given a number, say 900, prints the smallest palindrome larger than the number, 909 in this case. I gave a brute force solution that checks every number, but I guess there is a better way to do this.

+3
source share
3 answers

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

If the resulting number is less than the original, increase the center digit / center by 2 digits per unit. If they are 9, set them to zero and try again with two digits next to them, moving outward until you press non-9.

Edit:

, , -9, 1 , , , 0, - 1. , 2 .

+3

, Python ( , 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])

:

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

, , . :)

, .

1) - 9 . , "9 9 9". "1 0 0 1"

2) . , "1 2 3 4". "1 3 3 1"

3) - 9. "1 2 2 1". "1 3 3 1".

1  . n + 1 , 1, 0.

2 3. :

Left Side: . "1 2 3 4 5 6" "1 2 3", "1 2 3 4 5" "1 2"

Right Side: . "1 2 3 4 5 6" - "4 5 6", "1 2 3 4 5" - "4 5", , , . , , , .

, . , -. . .

j. ( , n ). j .

Step 1. , . , "8 3 4 2 2 4 6 9", . 3, j 6.

Step 2. 1 :

Case 1: j . , . 1 ( , n ) MSB . , "1 2 9 2 1", 9 10 , "1 3 0 3 1"

Case 2: , . , , , . -.

2.1) , , - . . "7 8 3 3 2 2" - "7 8 3 3 8 7" "1 2 5 3 2 2" "1 2 5 5 2 1" "1 4 5 8 7 6 7 8 3 2 2" "1 4 5 8 7 6 7 8 5 4 1" ? , , 1. . , , , .

2.2) . , . . "7 1 3 3 2 2" - "7 1 4 4 1 7" "1 2 3 4 6 2 8" "1 2 3 5 3 2 1" "9 4 1 8 7 9 7 8 3 2 2" "9 4 1 8 8 0 8 8 1 4 9" , , Case 1. 1 ( ase n ) MSB .

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

0

More articles:


All Articles