I want to solve the following problem: Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers. Here is what I have tried:

def nearestPalindromic(n: str) -> str:
    # Convert input string n to integer
    original_n = int(n)
    
    # Calculate the length of the number as a string
    str_n = str(original_n)
    length = len(str_n)
    
    # Special case: single digit numbers
    if length == 1:
        return str(original_n)
    
    # Create the base palindrome by mirroring the left half
    left_half = str_n[:(length + 1) // 2]  # Left half including middle if odd
    mirrored = int(left_half + left_half[-(length // 2):][::-1])

    # Create candidates by modifying the left half
    left_num = int(left_half)
    
    lower_half = str(left_num - 1)  # Decrease left half
    upper_half = str(left_num + 1)  # Increase left half
    
    lower_pal = int(lower_half + lower_half[-(length // 2):][::-1])
    upper_pal = int(upper_half + upper_half[-(length // 2):][::-1])
    
    # Handle edge cases like 1000 -> 999, or 9999 -> 10001
    edge_case = 10 ** (length - 1) - 1  # 999 for 1000
    large_case = 10 ** length + 1  # 10001 for 9999
    
    # List of all candidates
    candidates = [mirrored, lower_pal, upper_pal, edge_case, large_case]
    
    # Exclude the original number from candidates
    candidates = [c for c in candidates if c != original_n]
    
    # Find the closest palindrome using the key that compares by absolute difference first,
    # and by value second for ties
    closest = min(candidates, key=lambda x: (abs(x - original_n), x))
    
    # Return the result as a string
    return str(closest)

but I get this error:

Input
n =
"123"
Output
122
Expected
"121"

I want to solve the following problem: Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers. Here is what I have tried:

def nearestPalindromic(n: str) -> str:
    # Convert input string n to integer
    original_n = int(n)
    
    # Calculate the length of the number as a string
    str_n = str(original_n)
    length = len(str_n)
    
    # Special case: single digit numbers
    if length == 1:
        return str(original_n)
    
    # Create the base palindrome by mirroring the left half
    left_half = str_n[:(length + 1) // 2]  # Left half including middle if odd
    mirrored = int(left_half + left_half[-(length // 2):][::-1])

    # Create candidates by modifying the left half
    left_num = int(left_half)
    
    lower_half = str(left_num - 1)  # Decrease left half
    upper_half = str(left_num + 1)  # Increase left half
    
    lower_pal = int(lower_half + lower_half[-(length // 2):][::-1])
    upper_pal = int(upper_half + upper_half[-(length // 2):][::-1])
    
    # Handle edge cases like 1000 -> 999, or 9999 -> 10001
    edge_case = 10 ** (length - 1) - 1  # 999 for 1000
    large_case = 10 ** length + 1  # 10001 for 9999
    
    # List of all candidates
    candidates = [mirrored, lower_pal, upper_pal, edge_case, large_case]
    
    # Exclude the original number from candidates
    candidates = [c for c in candidates if c != original_n]
    
    # Find the closest palindrome using the key that compares by absolute difference first,
    # and by value second for ties
    closest = min(candidates, key=lambda x: (abs(x - original_n), x))
    
    # Return the result as a string
    return str(closest)

but I get this error:

Input
n =
"123"
Output
122
Expected
"121"

• python

Share Improve this question Follow edited Mar 16 at 21:15 mkrieger1 23.5k77 gold badges6464 silver badges8282 bronze badges asked Mar 16 at 21:00 ttinattina 9733 silver badges1010 bronze badges 2

• Why does the function return 122 instead of 121? (Or why did you expect your code to return 121?) – mkrieger1 Commented Mar 16 at 21:16
• Is 121 even included in candidates? If not, why do you think it should be? And why is 122 apparently included in candidates if it is not a palindrome? – mkrieger1 Commented Mar 16 at 21:24

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 0

The way you are mirroring the left half is wrong, try:

mirrored = int(left_half + left_half[:(length // 2)][::-1])

I would condense it to:

def is_palindrom(n: str) -> str:
    if len(n) <= 1:
        return True
    idx = len(n)//2
    return n[:idx] == n[:-idx-1**len(n):-1]

def nearest_palindrom(n: str) -> str:
    i = 1
    while True:
        if is_palindrom(f"{int(n) - i}"):
            return f"{int(n) - i}"
        elif is_palindrom(f"{int(n) + i}"):
            return f"{int(n) + i}"
        i += 1

And as you see separate the is_palindrom test from the rest.

Less efficient but more beautiful - since simple is:

def is_palindrom(n: str) -> str:
    if len(n) <= 1:
        return True
    return n == n[::-1]

def nearest_palindrom(n: str) -> str:
    i = 1
    while True:
        if is_palindrom(f"{int(n) - i}"):
            return f"{int(n) - i}"
        elif is_palindrom(f"{int(n) + i}"):
            return f"{int(n) + i}"
        i += 1