Problem

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

Examples

Example 1:

1
2
3
4

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:

1
2
3
4

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:

1
2
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

Solution

Method 1 – BFS Enumeration (Shortest Valid Multiple)

Intuition

We want the smallest number > k, a multiple of k, and made only of two digits. This is a classic shortest-path-in-string-space problem, solved by BFS: generate numbers by appending allowed digits, and check divisibility and size.

Approach

  1. Use BFS starting from all non-zero allowed digits (to avoid leading zeros).
  2. For each number, append either digit1 or digit2 to the end, and check if the new number is a valid answer.
  3. Stop if the number exceeds 2^31-1.
  4. Return the first valid number found, or -1 if none exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <queue>
#include <string>
using namespace std;
class Solution {
public:
    int findInteger(int k, int d1, int d2) {
        if (d1 == 0 && d2 == 0) return -1;
        queue<long long> q;
        for (int d : {d1, d2}) {
            if (d != 0) q.push(d);
        }
        while (!q.empty()) {
            long long x = q.front(); q.pop();
            if (x > k && x % k == 0) return x <= INT32_MAX ? (int)x : -1;
            if (x > INT32_MAX / 10) continue;
            for (int d : {d1, d2}) {
                long long nx = x * 10 + d;
                if (nx > INT32_MAX) continue;
                q.push(nx);
            }
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;
class Solution {
    public int findInteger(int k, int d1, int d2) {
        if (d1 == 0 && d2 == 0) return -1;
        Queue<Long> q = new LinkedList<>();
        for (int d : new int[]{d1, d2}) {
            if (d != 0) q.offer((long)d);
        }
        while (!q.isEmpty()) {
            long x = q.poll();
            if (x > k && x % k == 0) return x <= Integer.MAX_VALUE ? (int)x : -1;
            if (x > Integer.MAX_VALUE / 10) continue;
            for (int d : new int[]{d1, d2}) {
                long nx = x * 10 + d;
                if (nx > Integer.MAX_VALUE) continue;
                q.offer(nx);
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from collections import deque
class Solution:
    def findInteger(self, k, d1, d2):
        if d1 == 0 and d2 == 0:
            return -1
        q = deque()
        for d in {d1, d2}:
            if d != 0:
                q.append(d)
        while q:
            x = q.popleft()
            if x > k and x % k == 0:
                return x if x <= 2**31-1 else -1
            if x > (2**31-1) // 10:
                continue
            for d in {d1, d2}:
                nx = x * 10 + d
                if nx > 2**31-1:
                    continue
                q.append(nx)
        return -1

Complexity

  • ⏰ Time complexity: O(N) — BFS explores numbers in increasing order, but N is limited by 2^31-1 and k.
  • 🧺 Space complexity: O(N) — For the BFS queue.