Find the Next Larger Palindrome
Company: Uber
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a positive integer `n`, return the smallest integer strictly greater than `n` whose decimal representation is a palindrome.
A palindrome reads the same from left to right and right to left. Do not allow leading zeros.
Examples:
- `n = 9` -> `11`
- `n = 123` -> `131`
- `n = 808` -> `818`
- `n = 999` -> `1001`
Discuss edge cases such as single-digit inputs, numbers consisting only of `9`s, even versus odd digit lengths, and inputs that are already palindromes.
Quick Answer: This question evaluates proficiency in numeric and string manipulation, algorithmic thinking, and edge-case reasoning related to palindromic number generation.
Given a positive integer `n`, return the smallest integer strictly greater than `n` whose decimal representation is a palindrome.
A palindrome reads the same from left to right and right to left. The result must not contain leading zeros.
Examples:
- `9 -> 11`
- `123 -> 131`
- `808 -> 818`
- `999 -> 1001`
Be careful with edge cases such as single-digit inputs, numbers made entirely of `9`s, even versus odd digit lengths, and inputs that are already palindromes. A brute-force approach that checks every number after `n` is not efficient enough; instead, reason about how palindromes are formed.
Constraints
- 1 <= n < 10^18
- The returned palindrome must have no leading zeros
Examples
Input: (1,)
Expected Output: 2
Explanation: The next integer after 1 is 2, and every single-digit number is a palindrome.
Input: (9,)
Expected Output: 11
Explanation: After 9, the next palindrome is 11.
Hints
- Try building a palindrome by copying the left half of the number onto the right half.
- If that mirrored number is not strictly greater than `n`, increment the middle digit(s) and mirror again. Numbers like 9, 99, and 999 need special handling.