1999. Smallest Greater Multiple Made of Two Digits

Approach 1: BFS

• Time: $O(2^n)$
• Space: $O(2^n)$

C++JavaPython

class Solution {
 public:
  int findInteger(int k, int digit1, int digit2) {
    const int minDigit = min(digit1, digit2);
    const int maxDigit = max(digit1, digit2);
    const vector<int> digits = minDigit == maxDigit
                                   ? vector<int>{minDigit}
                                   : vector<int>{minDigit, maxDigit};
    queue<int> q;

    for (const int digit : digits)
      q.push(digit);

    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      if (u > k && u % k == 0)
        return u;
      if (u == 0)
        continue;
      for (const int digit : digits) {
        const long nextNum = u * 10L + digit;
        if (nextNum > INT_MAX)
          continue;
        q.push(nextNum);
      }
    }

    return -1;
  }
};

class Solution {
  public int findInteger(int k, int digit1, int digit2) {
    final int minDigit = Math.min(digit1, digit2);
    final int maxDigit = Math.max(digit1, digit2);
    final int[] digits =
        minDigit == maxDigit ? new int[] {minDigit} : new int[] {minDigit, maxDigit};
    Queue<Integer> q = new ArrayDeque<>();

    for (final int digit : digits)
      q.offer(digit);

    while (!q.isEmpty()) {
      final int u = q.poll();
      if (u > k && u % k == 0)
        return u;
      if (u == 0)
        continue;
      for (final int digit : digits) {
        final long nextNum = u * 10L + digit;
        if (nextNum > Integer.MAX_VALUE)
          continue;
        q.offer((int) nextNum);
      }
    }

    return -1;
  }
}

class Solution:
  def findInteger(self, k: int, digit1: int, digit2: int) -> int:
    minDigit = min(digit1, digit2)
    maxDigit = max(digit1, digit2)
    digits = [minDigit] if minDigit == maxDigit else [minDigit, maxDigit]
    q = collections.deque()

    for digit in digits:
      q.append(digit)

    while q:
      u = q.popleft()
      if u > k and u % k == 0:
        return u
      if u == 0:
        continue
      for digit in digits:
        nextNum = u * 10 + digit
        if nextNum > 2**31 - 1:
          continue
        q.append(nextNum)

    return -1

Approach 2: Recursive

• Time: $O(2^n)$
• Space: $O(2^n)$

C++JavaPython

class Solution {
 public:
  int findInteger(int k, int digit1, int digit2) {
    return findInteger(k, digit1, digit2, 0);
  }

 private:
  int findInteger(int k, int d1, int d2, long x) {
    if (x > INT_MAX)
      return -1;
    if (x > k && x % k == 0)
      return x;
    // Skip if d1/d2 and x are zero.
    const int a = (x + d1 == 0) ? -1 : findInteger(k, d1, d2, x * 10 + d1);
    const int b = (x + d2 == 0) ? -1 : findInteger(k, d1, d2, x * 10 + d2);
    if (a == -1)
      return b;
    if (b == -1)
      return a;
    return min(a, b);
  }
};

class Solution {
  public int findInteger(int k, int digit1, int digit2) {
    return findInteger(k, digit1, digit2, 0);
  }

  private int findInteger(int k, int d1, int d2, long x) {
    if (x > Integer.MAX_VALUE)
      return -1;
    if (x > k && x % k == 0)
      return (int) x;
    // Skip if d1/d2 and x are zero.
    final int a = (x + d1 == 0) ? -1 : findInteger(k, d1, d2, x * 10 + d1);
    final int b = (x + d2 == 0) ? -1 : findInteger(k, d1, d2, x * 10 + d2);
    if (a == -1)
      return b;
    if (b == -1)
      return a;
    return Math.min(a, b);
  }
}

class Solution:
  def findInteger(self, k: int, digit1: int, digit2: int) -> int:
    def dfs(x: int) -> int:
      if x > 2**31 - 1:
        return -1
      if x > k and x % k == 0:
        return x
      # Skip if digit1/digit2 and x are zero.
      a = -1 if x + digit1 == 0 else dfs(x * 10 + digit1)
      b = -1 if x + digit2 == 0 else dfs(x * 10 + digit2)
      if a == -1:
        return b
      if b == -1:
        return a
      return min(a, b)

    return dfs(0)