Question

1999. Smallest Greater Multiple Made of Two Digits

中文文档

Description

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. If no such integer exists or the integer exceeds the limit of a signed 32-bit integer (_231 - 1_), return _-1.

 

Example 1:

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.

Example 2:

Input: k = 3, digit1 = 4, digit2 = 2
Output: 24
Explanation:
24 is the first integer larger than 3, a multiple of 3, and comprised of only the digits 4 and/or 2.

Example 3:

Input: k = 2, digit1 = 0, digit2 = 0
Output: -1
Explanation:
No integer meets the requirements so return -1.

 

Constraints:

• 1 <= k <= 1000
• 0 <= digit1 <= 9
• 0 <= digit2 <= 9

Solutions

Solution 1

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)

class Solution {
  public int findInteger(int k, int digit1, int digit2) {
    if (digit1 == 0 && digit2 == 0) {
      return -1;
    }
    if (digit1 > digit2) {
      return findInteger(k, digit2, digit1);
    }
    Deque<Long> q = new ArrayDeque<>();
    q.offer(0L);
    while (true) {
      long x = q.poll();
      if (x > Integer.MAX_VALUE) {
        return -1;
      }
      if (x > k && x % k == 0) {
        return (int) x;
      }
      q.offer(x * 10 + digit1);
      if (digit1 != digit2) {
        q.offer(x * 10 + digit2);
      }
    }
  }
}

class Solution {
public:
  int findInteger(int k, int digit1, int digit2) {
    if (digit1 == 0 && digit2 == 0) {
      return -1;
    }
    if (digit1 > digit2) {
      swap(digit1, digit2);
    }
    queue<long long> q{{0}};
    while (1) {
      long long x = q.front();
      q.pop();
      if (x > INT_MAX) {
        return -1;
      }
      if (x > k && x % k == 0) {
        return x;
      }
      q.emplace(x * 10 + digit1);
      if (digit1 != digit2) {
        q.emplace(x * 10 + digit2);
      }
    }
  }
};

func findInteger(k int, digit1 int, digit2 int) int {
  if digit1 == 0 && digit2 == 0 {
    return -1
  }
  if digit1 > digit2 {
    digit1, digit2 = digit2, digit1
  }
  q := []int{0}
  for {
    x := q[0]
    q = q[1:]
    if x > math.MaxInt32 {
      return -1
    }
    if x > k && x%k == 0 {
      return x
    }
    q = append(q, x*10+digit1)
    if digit1 != digit2 {
      q = append(q, x*10+digit2)
    }
  }
}