Smallest Larger Integer That Uses None of the Digits of n

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

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

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.

Example 3

Input:  n = 123456789
Output: -1

The only digit that is not forbidden is 0, and no positive integer can be written with zeros alone.

Smallest Larger Integer Avoiding the Digits of n

Hints

1. Start by working out which digits are still allowed, and decide when no positive integer can be written with them at all.
2. 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.
3. 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.

Approach

Let A be the set of digits that do not appear in n, and let L be the number of digits of n. If A has no nonzero digit (A is empty, or A contains only 0), no positive integer can be written with A, so the answer is -1. Otherwise an answer always exists, because a nonzero digit of A repeated L + 1 times exceeds n.

Key observation: the leading digit of n is itself forbidden, so every L-digit candidate built from A already differs from n in its first position. Such a candidate is greater than n exactly when its first digit is greater than the first digit of n. Every candidate with fewer than L digits is smaller than n, and every candidate with more than L digits is larger than every L-digit candidate.

Algorithm: if A contains a digit greater than the first digit of n, the answer has L digits: the smallest such digit, followed by L - 1 copies of the smallest digit of A (which may be 0). Otherwise the answer has L + 1 digits: the smallest nonzero digit of A, followed by L copies of the smallest digit of A. In both branches the lead alone makes the number valid and greater than n, so filling every remaining position with the smallest allowed digit gives the minimum.

Edge cases: single-digit n (9 gives 10), 0 forbidden so the fill digit is the smallest nonzero allowed digit (90 gives 111), only 0 allowed or all ten digits present (-1), and answers above 2^31 - 1 with up to 11 digits (2034567899 gives 11111111111), which is why Java returns long and C++ returns long long.

• Time complexity: O(log n)
• Space complexity: O(log n)