Smallest Larger Integer That Uses None of the Digits of n
Company: Elevenlabs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Given a positive integer `n`, return the smallest integer that is strictly greater than `n` and that contains none of the decimal digits appearing in `n`. If no such integer exists, return `-1`.
### Function Signature
```python
def next_number(n: int) -> int:
```
### Rules
- Digits are read in ordinary base-10 notation, without leading zeros.
- A digit is forbidden if it appears at least once in `n`. Every digit of the returned integer must be a digit that is not forbidden. The returned integer may repeat a digit any number of times, as `700000` does in Example 1.
- The returned integer has no leading zeros, so its first digit is not `0`. It may have more digits than `n`.
- Return `-1` exactly when no positive integer greater than `n` can be written using only digits that are not forbidden.
### Constraints
- `1 <= n <= 2^31 - 1` (that is, `n` is strictly positive and less than `2147483648`)
- The returned value can exceed `2^31 - 1`, so it may need a 64-bit or arbitrary-precision integer; it is always less than `10^11`.
### Examples
**Example 1**
```text
Input: n = 654321
Output: 700000
```
The forbidden digits are 1, 2, 3, 4, 5 and 6. Every integer from 654322 to 699999 starts with a 6, and 700000 uses only the allowed digits 7 and 0.
**Example 2**
```text
Input: n = 90
Output: 111
```
The forbidden digits are 9 and 0. Every integer from 91 to 99 contains a 9, every integer from 100 to 110 contains a 0, and 111 contains neither.
**Example 3**
```text
Input: n = 123456789
Output: -1
```
The only digit that is not forbidden is 0, and no positive integer can be written with zeros alone.
Overview: Given a positive integer below 2^31, find the smallest integer strictly greater than it that uses none of its decimal digits, or return -1 when no such integer exists. The problem tests reasoning about allowed digit sets, leading zeros, answers longer than the input, and results that exceed the 32-bit range.
Read the full Elevenlabs Software Engineer interview experience this question came from
Given a positive integer `n`, return the smallest integer that is strictly greater than `n` and that contains none of the decimal digits appearing in `n`. If no such integer exists, return `-1`.
Rules:
- Digits are read in ordinary base-10 notation, without leading zeros.
- A digit is forbidden if it appears at least once in `n`. Every digit of the returned integer must be a digit that is not forbidden. The returned integer may repeat a digit any number of times, as `700000` does in Example 1.
- The returned integer has no leading zeros, so its first digit is not `0`. It may have more digits than `n`.
- Return `-1` exactly when no positive integer greater than `n` can be written using only digits that are not forbidden.
Constraints:
- `1 <= n <= 2^31 - 1` (that is, `n` is strictly positive and less than `2147483648`).
- The returned value can exceed `2^31 - 1`, so it needs a 64-bit integer (Java returns `long`, C++ returns `long long`); it is always less than `10^11`.
Example 1:
Input: n = 654321
Output: 700000
The forbidden digits are 1, 2, 3, 4, 5 and 6. Every integer from 654322 to 699999 starts with a 6, and 700000 uses only the allowed digits 7 and 0.
Example 2:
Input: n = 90
Output: 111
The forbidden digits are 9 and 0. Every integer from 91 to 99 contains a 9, every integer from 100 to 110 contains a 0, and 111 contains neither.
Constraints
- 1 <= n <= 2^31 - 1 (n is strictly positive and less than 2147483648)
- The returned value can exceed 2^31 - 1 (use long in Java and long long in C++); it is always less than 10^11
- Return -1 exactly when no positive integer greater than n can be written using only digits that do not appear in n
Examples
Input: (1,)
Expected Output: 2
Explanation: Minimum valid input: only digit 1 is forbidden, so the next integer 2 is the answer.
Input: (5,)
Expected Output: 6
Explanation: Singleton: 1-4 are allowed but smaller than 5; the lead must exceed 5, so the answer is 6, not the smallest allowed digit 1.
Hints
- Start by working out which digits are still allowed, and decide when no positive integer can be written with them at all.
- Think about how many digits the answer can have compared with n, and what decides whether an answer with exactly as many digits as n exists.
- Once the first digit of the answer is fixed, ask how the remaining positions should be filled to keep the number as small as possible, remembering that the first digit cannot be 0.