Problem Description

You need to find the smallest integer that satisfies three conditions:

1. The integer must be larger than a given value k
2. The integer must be a multiple of k (divisible by k with no remainder)
3. The integer can only contain the digits digit1 and/or digit2

For example, if k = 15, digit1 = 1, and digit2 = 5, you need to find the smallest number greater than 15, divisible by 15, and made up of only the digits 1 and 5. Valid candidates would include numbers like 15, 51, 55, 111, 115, 151, 155, 511, 515, 551, 555, etc. Among these, you'd need to find which ones are divisible by 15 and greater than 15, then return the smallest one.

The solution uses a breadth-first search (BFS) approach with a queue. Starting from 0, it builds numbers by appending digit1 and digit2 at each step. The BFS ensures we explore smaller numbers first. The algorithm:

1. Handles the edge case where both digits are 0 (impossible to form a valid number)
2. Swaps digits if needed to ensure digit1 ≤ digit2 for consistency
3. Uses a queue starting with 0
4. For each number x in the queue:
   • Checks if it exceeds the 32-bit integer limit (2^31 - 1)
   • Returns x if it's greater than k and divisible by k
   • Otherwise, generates new numbers by appending digit1 and digit2 to x
5. Avoids duplicates when digit1 == digit2

If no valid integer exists within the 32-bit integer range, the function returns -1.

Intuition

The key insight is that we need to systematically generate numbers using only two specific digits and find the smallest one that meets our criteria. Think of it like building numbers digit by digit, where at each position we can only choose from our two allowed digits.

Why BFS? When building numbers by appending digits, smaller numbers naturally come before larger ones. If we start with 0 and keep appending digits, a number like 15 will be generated before 151 or 515. This ordering property of BFS guarantees that the first valid number we find will be the smallest.

Consider how numbers grow when we append digits: starting from any number x, we can create x * 10 + digit1 and x * 10 + digit2. For example, from 5, we can create 51 and 55 (if our digits are 1 and 5). This forms a tree-like structure where each level represents numbers with one more digit than the previous level.

The approach of starting from 0 is clever because:

• From 0, we can generate single-digit numbers (digit1 and digit2)
• From single-digit numbers, we generate two-digit numbers
• This continues level by level, ensuring we explore all possible combinations

Why check for divisibility and size at each step rather than generating all possibilities first? Because we want to stop as soon as we find a valid answer. Since BFS explores in increasing order, the first number that satisfies both conditions (greater than k and divisible by k) is guaranteed to be the smallest such number.

The 32-bit limit check (2^31 - 1) serves as a termination condition. If we've built numbers this large without finding a valid answer, either no solution exists or it would exceed integer limits.

Learn more about Math patterns.

Solution Approach

The implementation uses a BFS with a queue data structure to systematically generate and check numbers:

1. Handle Edge Cases:

if digit1 == 0 and digit2 == 0:
    return -1

If both digits are 0, we can't form any positive number, so return -1 immediately.

2. Normalize Input:

if digit1 > digit2:
    return self.findInteger(k, digit2, digit1)

Swap the digits to ensure digit1 ≤ digit2. This simplifies the logic and doesn't affect the result since we're using both digits anyway.

3. Initialize BFS Queue:

q = deque([0])

Start with 0 in the queue. This serves as the root of our number generation tree.

4. BFS Loop:

while 1:
    x = q.popleft()

Process numbers in FIFO order, ensuring we explore smaller numbers first.

5. Check Termination Conditions:

if x > 2**31 - 1:
    return -1

If the current number exceeds the 32-bit integer limit, no valid solution exists within bounds.

6. Check for Valid Answer:

if x > k and x % k == 0:
    return x

If the current number is both greater than k and divisible by k, we've found our answer. Since BFS explores in increasing order, this is guaranteed to be the smallest such number.

7. Generate Next Numbers:

q.append(x * 10 + digit1)
if digit1 != digit2:
    q.append(x * 10 + digit2)

Create new numbers by appending each digit to the current number. The formula x * 10 + digit shifts the existing number left by one decimal place and adds the new digit. The condition digit1 != digit2 prevents adding duplicate numbers when both digits are the same.

Example Walkthrough: For k = 15, digit1 = 1, digit2 = 5:

• Start: queue = [0]
• Process 0: Add 1 and 5 → queue = [1, 5]
• Process 1: Add 11 and 15 → queue = [5, 11, 15]
• Process 5: Add 51 and 55 → queue = [11, 15, 51, 55]
• Process 11: Not divisible by 15, continue
• Process 15: Equal to k (not greater), continue
• Process 51: Greater than 15 but not divisible by 15, continue
• Process 55: Greater than 15 but not divisible by 15, continue
• Continue until finding 555 which is both > 15 and divisible by 15

The BFS guarantees we find 555 before exploring larger numbers like 1155 or 5115.

Example Walkthrough

Let's trace through the algorithm with k = 12, digit1 = 2, digit2 = 4:

Goal: Find the smallest number > 12, divisible by 12, using only digits 2 and 4.

Step-by-step BFS execution:

1. Initialize: queue = [0]

2. Process 0:

   • Check: 0 > 12? No. 0 % 12 = 0? Yes (but not > 12)
   • Generate: 0 * 10 + 2 = 2, 0 * 10 + 4 = 4
   • Queue becomes: [2, 4]

3. Process 2:

   • Check: 2 > 12? No
   • Generate: 2 * 10 + 2 = 22, 2 * 10 + 4 = 24
   • Queue becomes: [4, 22, 24]

4. Process 4:

   • Check: 4 > 12? No
   • Generate: 4 * 10 + 2 = 42, 4 * 10 + 4 = 44
   • Queue becomes: [22, 24, 42, 44]

5. Process 22:

   • Check: 22 > 12? Yes. 22 % 12 = 10? Not divisible
   • Generate: 22 * 10 + 2 = 222, 22 * 10 + 4 = 224
   • Queue becomes: [24, 42, 44, 222, 224]

6. Process 24:

   • Check: 24 > 12? Yes. 24 % 12 = 0? Yes!
   • Return 24 ✓

The answer is 24 - it's the smallest number greater than 12, divisible by 12, and made only of digits 2 and 4.

Why BFS finds this first: Notice how we explored all 1-digit numbers (2, 4) before any 2-digit numbers, and all 2-digit numbers (22, 24, 42, 44) before any 3-digit numbers. Since 24 is the smallest valid 2-digit number, we find it before checking larger candidates like 42, 44, or any 3-digit numbers.

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^n) where n is the number of digits in the result.

The algorithm uses BFS to explore all possible numbers that can be formed using digit1 and digit2. In the worst case:

• Each number in the queue can branch into at most 2 new numbers (one with digit1 appended and one with digit2 appended)
• If the result has n digits, we need to explore up to 2^n different combinations
• Each operation (checking divisibility, appending to queue) takes O(1) time
• The upper bound check x > 2^31 - 1 limits the maximum value, but in worst case we still explore exponentially many numbers before finding the answer or determining it's impossible

Space Complexity: O(2^n) where n is the number of digits in the result.

The space is dominated by the BFS queue:

• In the worst case, the queue can contain all numbers at a particular level of the BFS tree
• At level i, there can be up to 2^i numbers in the queue
• The maximum level is bounded by the number of digits in the result or when we exceed 2^31 - 1
• Therefore, the queue can grow up to O(2^n) elements in the worst case

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Leading Zero Handling

The current implementation has a subtle issue when one digit is 0 and the other is non-zero. When digit1 = 0 after swapping, the BFS will generate numbers with leading zeros (like 01, 05, 001, etc.), which are mathematically equivalent to their non-zero counterparts (1, 5, 1, etc.) but create unnecessary duplicates in the queue.

Problem Example:

• Input: k = 2, digit1 = 5, digit2 = 0
• After swap: digit1 = 0, digit2 = 5
• Queue progression: [0] → [0, 5] → [0, 5, 50] → ...
• The algorithm keeps adding 0 back to the queue, creating an infinite loop of zeros

Solution: Skip appending when the result would be a leading zero:

# Generate new numbers by appending digit1
if not (current_num == 0 and digit1 == 0):
    queue.append(current_num * 10 + digit1)

# Generate new numbers by appending digit2
if digit1 != digit2:
    if not (current_num == 0 and digit2 == 0):
        queue.append(current_num * 10 + digit2)

2. Memory Overflow from Duplicate States

Without proper visited tracking, the queue can grow exponentially with duplicate numbers, especially when exploring larger search spaces. While BFS guarantees finding the smallest valid number first, it doesn't prevent revisiting the same numbers through different paths.

Problem Example:

• For large values of k with no valid solution in reasonable range
• The queue keeps growing with all possible combinations until hitting the 32-bit limit
• This causes memory issues before returning -1

Solution: Add a visited set to track processed numbers:

visited = set()
queue = deque([0])

while queue:
    current_num = queue.popleft()
  
    if current_num in visited:
        continue
    visited.add(current_num)
  
    # Rest of the logic...

3. Incorrect Handling of k = 0

The current implementation doesn't explicitly handle k = 0, which would cause a division by zero error when checking current_num % k == 0.

Solution: Add an edge case check at the beginning:

if k == 0:
    return -1  # No number can be divisible by 0

4. Inefficient Search for Large k Values

When k is very large, the BFS explores many unnecessary small numbers that could never satisfy the "greater than k" condition. This wastes computational resources.

Solution: Start the BFS from a number closer to k rather than 0:

# Start from the smallest number made of digit1 and digit2 that's >= k
start_candidates = []
if digit1 > 0:
    start_candidates.append(digit1)
if digit2 > 0 and digit1 != digit2:
    start_candidates.append(digit2)

queue = deque(start_candidates) if start_candidates else deque([0])