Leetcode 1999 Smallest Greater Multiple Made of Two Digits

Problem statement

https://leetcode.com/problems/smallest-greater-multiple-made-of-two-digits/

Solution

One of the ways to solve this problem is to use queue, where each time we extract number x and add numbers x*10 + d1 and x*10 + d2. Be careful to add only bigger number then we have, for example if x = 0 and d1 = 0, we do not add 0 again. First time when we have number divisible by k, we return it. If we did not found it, return -1

Complexity

Time complexity is O(2^m), where m is maximum number of digits we can have. Space complexity is the same.

Code

class Solution:
    def findInteger(self, k, d1, d2):
        q = deque([0])
        cands = sorted(set([d1, d2]))
        
        while q:
            num = q.popleft()
            if num > k and num % k == 0: return num
            if num >= 2**31: return -1
            for cand in cands:
                if num*10 + cand != num:
                    q.append(num*10 + cand)
                    
        return -1