Problem Statement:

Given a positive integer n, find the smallest palindrome greater than n using the same digits as n. Return -1 if no such palindrome exists.

Example:

Input: n = 1234 Output: 1243

Input: n = 2345 Output: 2352

Input: n = 999 Output: -1

Solution:

To solve this problem, we need to consider all the possible permutations of the digits in n. We can start by finding the next greater permutation of digits in n. If that permutation is a palindrome, then we have our answer. Otherwise, we need to find the next greater permutation of digits that is a palindrome.

To find the next greater permutation, we can follow the below approach:

1. Traverse the digits from right to left and find the first digit that is smaller than the digit on its right. Let this digit be called the pivot.

2. Again traverse the digits from right to left and find the first digit that is greater than the pivot.

3. Swap the pivot with this greater digit.

4. Reverse the digits to the right of the pivot.

If there is no pivot in step 1, then the digits are already in descending order, and we cannot form a greater permutation.

Now, we have the next greater permutation. If it is a palindrome, we return it as the answer. Otherwise, we need to find the next greater permutation that is a palindrome.

To do that, we can follow the below steps:

1. Initialize two pointers p1 and p2. p1 starts at the first digit, and p2 starts at the last digit.

2. If the digit at p1 is greater than the digit at p2, then we need to swap the digits and continue.

3. If the digit at p1 is smaller than the digit at p2, then we need to replace p2 with the next greater digit and make the right side of the number palindrome.

4. If we cannot find a digit greater than the digit at p2, we need to move p1 to the next digit and repeat steps 2 to 4 until we find a palindrome.

If we cannot find a palindrome in the above steps, then there is no such palindrome that is greater than n, and we return -1.

Here is the Python code for the solution:

def next_palindrome_using_same_digits(n: int) -> int:

# Convert the number into a list of digits
digits = [int(d) for d in str(n)]

# Find the next greater permutation of the digits
pivot = len(digits) - 2
while pivot >= 0 and digits[pivot] >= digits[pivot + 1]:
    pivot -= 1
if pivot == -1:
    return -1
greater = len(digits) - 1
while digits[greater] <= digits[pivot]:
    greater -= 1
digits[pivot], digits[greater] = digits[greater], digits[pivot]
digits[pivot + 1:] = reversed(digits[pivot + 1:])

# Check if the next greater permutation is a palindrome
if digits == digits[::-1]:
    return int(''.join(map(str, digits)))

# Find the next greater permutation that is a palindrome
p1, p2 = 0, len(digits) - 1
while p1 < p2:
    if digits[p1] > digits[p2]:
        digits[p2] = digits[p1]
    elif digits[p1] < digits[p2]:
        greater = len(digits) - 1
        while digits[greater] <= digits[p1]:
            greater -= 1
        digits[greater], digits[p1] = digits[p1], digits[greater]
        digits[p2:] = reversed(digits[p2:])
        break
    p1 += 1
    p2 -= 1

# If we could not find a palindrome, return -1
if digits != digits[::-1]:
    return -1

return int(''.join(map(str, digits)))

Example case

print(next_palindrome_using_same_digits(1234)) # Output: 1243

Example case

print(next_palindrome_using_same_digits(2345)) # Output: 2352

Example case

print(next_palindrome_using_same_digits(999)) # Output: -1

Time Complexity:

Finding the next greater permutation takes O(n) time, where n is the number of digits in the input number. Finding the next greater permutation that is a palindrome also takes O(n) time. Therefore, the overall time complexity of the solution is O(n).

1