today Question

Next Smallest Palindrome

Difficulty: Hard

Given a number, in the form of an array num[] containing digits from 1 to 9(inclusive). Find the next smallest palindrome strictly larger than the given number.

Answers :::

Intuition

The core idea is that a palindrome is determined by its left half. Since we want the smallest number larger than the current one, we should try to change the number as little as possible. The most significant digits are on the left, so we try to keep the left half the same and "mirror" it to the right.

• Mirroring: If we mirror the left half to the right, we create a palindrome.
  • If this new palindrome is already greater than the original number, we have found our answer!
  • If it is smaller or equal, we must increment the number. To keep it the "smallest" next palindrome, we increment at the most "central" point (the middle digit) and then mirror again.

Approach

We can break the logic into three main steps:

Step A: Handle the "All 9s" Case

If the input is 999, the next palindrome isn't just a modification of these digits; it adds a digit: 1001.

• Logic: If all digits are 9, return 1 followed by n-1 zeros and another 1.

Step B: The Mirror Test

Compare the original right half with the mirrored left half to see if mirroring alone is enough.

1. Find the first pair of digits (moving from the center outwards) that are different.
2. If the digit on the left side is greater than the one on the right, mirroring the left half will result in a larger number.

   • Example: 13211  Left is 13, Right is 11. Mirroring gives 13231. Since 3 > 1, 13231 > 13211. Done!

     →→