Smallest Palindrome Strictly Greater Than K
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A **palindrome** is a positive integer whose decimal representation reads the same forwards and backwards, with no leading zeros. For example, `7`, `44`, `121`, and `3773` are palindromes; `10` and `120` are not.
Given a positive integer `K`, return the smallest palindrome that is **strictly greater** than `K`.
## Examples
**Example 1**
```
Input: K = 123
Output: 131
```
The palindromes near 123 are 121 and 131; the smallest one strictly greater than 123 is 131.
**Example 2**
```
Input: K = 99
Output: 101
```
99 is itself a palindrome, but the answer must be strictly greater than K, and 100 is not a palindrome.
**Example 3**
```
Input: K = 131
Output: 141
```
**Example 4**
```
Input: K = 12932
Output: 13031
```
Mirroring the left half of 12932 gives 12921, which is too small, so the middle must be incremented before mirroring.
**Example 5**
```
Input: K = 9999
Output: 10001
```
When K consists of all 9s, the answer has one more digit.
## Constraints
- `1 <= K < 10^18` (fits in a signed 64-bit integer, and so does the answer)
- Your solution should run in time proportional to the number of digits of `K` (up to a small polynomial factor). Incrementing and re-checking one number at a time is too slow: consecutive palindromes near `10^18` can be roughly `10^9` apart.
## Output
Return the answer as an integer.
Quick Answer: This question evaluates a candidate's ability to manipulate numeric digit representations, design an efficient constructive algorithm for special-form numbers, and reason about edge cases and complexity constraints.
A **palindrome** is a positive integer whose decimal representation reads the same forwards and backwards, with no leading zeros. For example, `7`, `44`, `121`, and `3773` are palindromes; `10` and `120` are not.
Given a positive integer `K`, return the smallest palindrome that is **strictly greater** than `K`.
### Examples
- `K = 123` -> `131` (the palindromes near 123 are 121 and 131; the smallest strictly greater than 123 is 131).
- `K = 99` -> `101` (99 is itself a palindrome, but the answer must be strictly greater; 100 is not a palindrome).
- `K = 131` -> `141`.
- `K = 12932` -> `13031` (mirroring the left half gives 12921, too small, so the middle must be incremented before mirroring).
- `K = 9999` -> `10001` (when K is all 9s, the answer has one more digit).
### Approach note
Incrementing and re-checking one number at a time is too slow: consecutive palindromes near `10^18` can be roughly `10^9` apart. Build the answer directly by mirroring the left half of `K`; if that is not strictly greater than `K`, increment the middle prefix and mirror again, handling the all-9s carry that adds a digit.
Constraints
- 1 <= K < 10^18 (K and the answer both fit in a signed 64-bit integer)
- Solution must run in time proportional to the number of digits of K (up to a small polynomial factor)
- Brute-force increment-and-check is too slow: gaps between consecutive palindromes near 10^18 can be ~10^9
Examples
Input: 123
Expected Output: 131
Explanation: 121 <= 123, so increment the prefix 12 -> 13 and mirror to 131.
Input: 99
Expected Output: 101
Explanation: 99 is a palindrome but not strictly greater; the prefix 9 carries to 10, adding a digit -> 101.
Hints
- The left half of K determines the palindrome: mirror it onto the right half to get a candidate palindrome of the same length.
- If the mirrored candidate is not strictly greater than K, increment the left-half prefix (including the middle digit for odd lengths) by one, then mirror again.
- Watch the carry: if incrementing the prefix adds a digit (K is all 9s, like 999 or 9999), the answer has one more digit and looks like 1 followed by zeros followed by 1 (e.g. 1001, 10001).