Katkat
Back

Smallest Larger Integer That Uses None of the Digits of n

ElevenlabsSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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.