Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go

• 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);
              }
          }
      }
  };
  

• 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)
  
  

• 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)
  		}
  	}
  }
  

All Problems

All Solutions