Find The Closest Palindrome - Leetcode Solution

Problem:

Given an integer n, find the closest palindrome number to n.

A palindrome number is defined as a number that remains the same when its digits are reversed. For example, 121 is a palindrome number.

If there is a tie, return the smaller palindrome number as the answer.

Example:

Input: n = 1215 Output: 1221 Explanation: The closest palindrome number to 1215 is 1221, which is a palindrome number.

Input: n = 123456 Output: 123321 Explanation: The closest palindrome number to 123456 is 123321, which is a palindrome number.

Approach:

The approach to solve this problem is to find the next palindrome number greater than n and the next palindrome number smaller than n. Then we can compare the absolute difference of these two palindrome numbers with n and return the smaller one.

Given a number n, we can find the next palindrome number greater than n by first converting the number to an array of digits. Then, we start from the middle and move towards the ends of the array. If the digits on both ends are not equal, we can change one of them to make them equal and continue our search. If the digit in the middle is less than 9, we can increase it by 1 and return the array as the next palindrome number. If the digit in the middle is already 9, we have to set it to 0 and continue our search.

Similarly, we can find the next palindrome number smaller than n by following the same approach, starting from the middle and moving towards the ends of the array.

Once we have the next palindrome numbers greater than and smaller than n, we can compare their absolute differences with n and return the smaller palindrome number.

Solution in Python:

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        # helper function to convert array of digits to integer
        def to_int(arr):
            num = 0
            for d in arr:
                num = num * 10 + d
            return num
        
        # helper function to convert integer to array of digits
        def to_arr(num):
            arr = []
            while num > 0:
                arr.append(num % 10)
                num //= 10
            return arr[::-1]
        
        # helper function to check if a number is palindrome
        def is_palindrome(arr):
            i, j = 0, len(arr) - 1
            while i < j:
                if arr[i] != arr[j]:
                    return False
                i += 1
                j -= 1
            return True
        
        # convert n to an array of digits
        arr = [int(x) for x in n]
        len_arr = len(arr)
        mid = len_arr // 2
        
        # search for next palindrome number greater than n
        i, j = mid - 1, mid + 1
        while i >= 0 and j < len_arr:
            if arr[i] != arr[j]:
                break
            i -= 1
            j += 1
        if i < 0 or j >= len_arr or arr[i] < arr[j]:
            arr[mid] += 1
            i, j = mid - 1, mid + 1
            while i >= 0 and j < len_arr:
                arr[j] = arr[i]
                i -= 1
                j += 1
        else:
            i, j = mid - 1, mid + 1
            while i >= 0 and j < len_arr:
                arr[j] = arr[i]
                i -= 1
                j += 1
                
        num1 = to_int(arr)
        
        # search for next palindrome number smaller than n
        arr = [int(x) for x in n]
        i, j = mid - 1, mid + 1
        while i >= 0 and j < len_arr:
            if arr[i] != arr[j]:
                break
            i -= 1
            j += 1
        if i < 0 or j >= len_arr or arr[i] > arr[j]:
            arr[mid] -= 1
            i, j = mid - 1, mid + 1
            while i >= 0 and j < len_arr:
                arr[j] = arr[i]
                i -= 1
                j += 1
            if arr[0] == 0:
                arr.pop(0)
                len_arr -= 1
                mid = len_arr // 2
                if len_arr < 2 or arr[mid] > 0:
                    arr[mid] -= 1
                else:
                    arr = [9] * (len_arr - 1)
                    arr.insert(0, 1)
        else:
            i, j = mid - 1, mid + 1
            while i >= 0 and j < len_arr:
                arr[j] = arr[i]
                i -= 1
                j += 1
        
        num2 = to_int(arr)
        
        # compare the absolute differences and return the smaller palindrome number
        if abs(num1 - int(n)) < abs(num2 - int(n)):
            return str(num1)
        elif abs(num1 - int(n)) > abs(num2 - int(n)):
            return str(num2)
        elif is_palindrome(to_arr(num1 - 1)):
            return str(num1 - 1)
        elif is_palindrome(to_arr(num1 + 1)):
            return str(num1 + 1)
        elif is_palindrome(to_arr(num2 - 1)):
            return str(num2 - 1)
        else:
            return str(num2 + 1)

Time Complexity:

The time complexity of this solution is O(n), where n is the number of digits in the input integer. We need to process the input integer two times to find the next palindrome numbers, and the time complexity of processing each digit is constant. We also need to check if each number we generate is a palindrome, which takes O(n) time. Finally, we need to compare the absolute differences of the two palindrome numbers with the input integer, which takes constant time. Therefore, the overall time complexity is O(n).

1