Given a number, find the next highest number that is a palindrome. For example:

• If the given number is 123, the next palindrome is 131.
• If the given number is 99, the next palindrome is 101.
• If the given number is 1221, the next palindrome is 1221 (as it is already a palindrome).
• If the given number is 899, the next palindrome is 909.
• If the given number is 999, the next palindrome is 1001.

Your task is to write a function that takes an integer as input and returns the next palindrome number. The palindrome must be strictly greater than the input number. Consider edge cases, such as when the input number consists of all 9s. What is the most efficient approach to solve this problem, and what is its time complexity?

Finding the Next Palindrome Number

This problem requires us to find the next palindrome number greater than a given input number. We'll explore different approaches, from a naive brute-force method to a more efficient solution.

1. Naive Approach (Brute Force)

The simplest approach is to increment the number by 1 and check if the new number is a palindrome. Repeat until a palindrome is found.

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def next_palindrome_naive(n):
    n += 1
    while not is_palindrome(n):
        n += 1
    return n

# Example Usage
number = 123
next_palindrome = next_palindrome_naive(number)
print(f"The next palindrome after {number} is {next_palindrome}") # Output: 131

Explanation:

1. is_palindrome(n): Checks if a number n is a palindrome by converting it to a string and comparing it with its reverse.
2. next_palindrome_naive(n): Increments n until is_palindrome(n) returns True.

2. Optimal Approach

A more efficient approach involves the following steps:

1. Handle edge cases like numbers consisting of all 9s.
2. Split the number into two halves (left and right).
3. If the left half is greater than the right half, create a palindrome by mirroring the left half.
4. If the left half is smaller or equal to the right half, increment the middle digit(s) and propagate the carry.

def next_palindrome(number):
    num_str = str(number)
    n = len(num_str)
    mid = n // 2

    # Handle the case where all digits are 9
    if all(digit == '9' for digit in num_str):
        return '1' + '0' * (n - 1) + '1'

    num_list = list(num_str)

    # Copy the left side to the right side
    for i in range(mid):
        num_list[n - 1 - i] = num_list[i]

    # Convert back to integer for comparison
    new_num = int("".join(num_list))

    # If the new number is greater than the original, return it
    if new_num > number:
        return new_num

    # Otherwise, increment the middle digit(s)
    i = mid - 1
    j = mid if n % 2 == 0 else mid + 1
    carry = 1

    while i >= 0 and carry:
        num_sum = int(num_list[i]) + carry
        num_list[i] = str(num_sum % 10)
        num_list[j] = num_list[i] # Mirror the change
        carry = num_sum // 10
        i -= 1
        j += 1

    # If there's still a carry, add it to the middle
    if carry:
        num_list.insert(0, '1')
        num_list[-1] = '1' # Mirror the change

    return int("".join(num_list))


# Example Usage
number = 123
next_palindrome = next_palindrome(number)
print(f"The next palindrome after {number} is {next_palindrome}")

number = 99
next_palindrome = next_palindrome(number)
print(f"The next palindrome after {number} is {next_palindrome}")

number = 1221
next_palindrome = next_palindrome(number)
print(f"The next palindrome after {number} is {next_palindrome}")

number = 899
next_palindrome = next_palindrome(number)
print(f"The next palindrome after {number} is {next_palindrome}")

number = 999
next_palindrome = next_palindrome(number)
print(f"The next palindrome after {number} is {next_palindrome}")

3. Time Complexity Analysis

• Naive Approach: O(k * n), where n is the number of digits and k is the number of iterations required to find the next palindrome. In the worst case, k can be large, making this approach inefficient.
• Optimal Approach: O(n), where n is the number of digits in the number. This is because we iterate through the digits at most once to mirror the left half and, in the worst case, to propagate the carry.

4. Space Complexity Analysis

• Naive Approach: O(n) due to the string conversion for palindrome checking.
• Optimal Approach: O(n) because we create a list of digits from the input number and possibly insert a new digit at the beginning.

5. Edge Cases and Handling

• All 9s: When the input number consists of all 9s (e.g., 99, 999), the next palindrome is of the form 10...01. The code handles this by creating a string with 1 at the beginning and end and 0s in between.
• Already a Palindrome: If the given number is already a palindrome, the algorithm still finds the next palindrome (which might be the same number if we allow equality, but the question specifies strictly greater than).
• Large Numbers: The code uses string representation to handle potentially very large numbers that might exceed integer limits.

Conclusion

The optimal approach provides a much more efficient solution with a time complexity of O(n) compared to the naive approach's O(k*n) complexity. The code also addresses important edge cases, ensuring robustness and correctness.