Smallest Greater Multiple Made of Two Digits — LeetCode 1999 Python Solution

The problem

Given three integers, k, digit1, and digit2, you want to find the smallest integer that is: Larger than k, A multiple of k, and Comprised of only the digits digit1 and/or digit2. Return the smallest such integer.

Example

Input

k = 2, digit1 = 0, digit2 = 2

Output

20

Explanation

20 is the first integer larger than 2, a multiple of 2, and comprised of only the digits 0 and/or 2.

Python solution

class Solution:
    def findInteger(self, k: int, digit1: int, digit2: int) -> int:
        if digit1 == 0 and digit2 == 0:
            return -1
        if digit1 > digit2:
            return self.findInteger(k, digit2, digit1)
        q = deque([0])
        while 1:
            x = q.popleft()
            if x > 2**31 - 1:
                return -1
            if x > k and x % k == 0:
                return x
            q.append(x * 10 + digit1)
            if digit1 != digit2:
                q.append(x * 10 + digit2)

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1999. Smallest Greater Multiple Made of Two Digits is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems