LeetCode 1999. Smallest Greater Multiple Made of Two Digits Solution in Java, C++, Python & Go | Explanation + Code

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

PythonJavaC++Go

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)(code-box)

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); } } } }(code-box)

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); } } } };(code-box)

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) } } }(code-box)