LeetCode 1999 - Smallest Greater Multiple Made of Two Digits

The problem asks us to find the smallest integer that satisfies three specific conditions. Given an integer k and two digits digit1 and digit2, we need an integer that is strictly larger than k, is a multiple of k, and consists only of the two given digits.

leetcodemediummathenumeration

LeetCode Problem 1999

Difficulty: 🟡 Medium
Topics: Math, Enumeration

Solution

Problem Understanding

The problem asks us to find the smallest integer that satisfies three specific conditions. Given an integer k and two digits digit1 and digit2, we need an integer that is strictly larger than k, is a multiple of k, and consists only of the two given digits. The integer must also fit within the 32-bit signed integer range, otherwise we return -1.

Inputs represent:

  • k: the base number whose multiples we are interested in, guaranteed to be between 1 and 1000.
  • digit1 and digit2: the only allowed digits in the target number, ranging from 0 to 9. They could be the same.

The output is a single integer: the smallest number that satisfies the three constraints, or -1 if it does not exist.

Key constraints to note include the relatively small maximum value of k (1000), meaning any multiple will be manageable, and that the resulting number may need to be arbitrarily large but still within a 32-bit signed integer range. Edge cases include:

  • Both digits being zero, which trivially yields no valid numbers.
  • One digit being zero, which cannot appear at the most significant position.
  • Very small k with large digits, which can produce very large numbers quickly.

Approaches

Brute Force

A brute-force approach would involve generating multiples of k one by one starting from k + 1. For each multiple, we would check if every digit belongs to the set {digit1, digit2}. This approach guarantees correctness because it systematically tests each possible candidate. However, it is inefficient because multiples of k can grow quickly, and the number of checks could be huge, especially if valid numbers have many digits.

Optimal Approach

The optimal approach uses Breadth-First Search (BFS) on the digits themselves rather than iterating multiples of k. The idea is to generate numbers using only the allowed digits in increasing order and check divisibility by k. This approach works efficiently because BFS guarantees the first valid number encountered is the smallest.

The key insight is:

  • Build numbers incrementally using digit1 and digit2.
  • Use BFS to ensure we examine numbers in increasing order.
  • Track remainders modulo k to avoid exploring unnecessary paths since (number * 10 + digit) % k gives the remainder for new numbers.

This allows us to prune vast numbers of possibilities and focus only on valid candidates.

Approach Time Complexity Space Complexity Notes
Brute Force O(L * k) O(1) Check every multiple of k until the result, potentially very large numbers
Optimal (BFS) O(k * 2^D) O(k) Generate numbers digit by digit using BFS, pruning by modulo

Algorithm Walkthrough

  1. Check if both digits are zero. If so, return -1 immediately.

  2. Initialize a queue with the non-zero starting digits. We avoid leading zeros.

  3. Maintain a visited set of remainders modulo k to prevent revisiting the same remainder, which would lead to repeated exploration.

  4. Perform BFS:

  5. Pop a number from the queue.

  6. Compute the remainder modulo k.

  7. If the remainder is zero and the number is greater than k, return it.

  8. Append both digit1 and digit2 to the current number (as strings), skip appending a leading zero.

  9. Push new numbers to the queue only if their remainder modulo k has not been visited.

  10. If BFS completes without finding a number, return -1.

Why it works: BFS guarantees that numbers are generated in increasing order. Using modulo k ensures we efficiently track potential multiples. Once we find a valid number with remainder zero, it is guaranteed to be the smallest possible number meeting all criteria.

Python Solution

from collections import deque

class Solution:
    def findInteger(self, k: int, digit1: int, digit2: int) -> int:
        if digit1 == 0 and digit2 == 0:
            return -1
        
        digits = sorted({digit1, digit2})
        queue = deque()
        visited = set()
        
        for d in digits:
            if d != 0:
                queue.append(str(d))
                visited.add(d % k)
        
        while queue:
            num_str = queue.popleft()
            num = int(num_str)
            rem = num % k
            
            if rem == 0 and num > k:
                if num > 2_147_483_647:
                    return -1
                return num
            
            for d in digits:
                new_num_str = num_str + str(d)
                new_rem = (rem * 10 + d) % k
                if new_rem not in visited:
                    visited.add(new_rem)
                    queue.append(new_num_str)
        
        return -1

The code initializes BFS with valid starting digits, tracks remainders modulo k to prune duplicate paths, and appends allowed digits to form new numbers. It stops as soon as a valid multiple greater than k is found.

Go Solution

package main

import (
	"fmt"
	"strconv"
)

func findInteger(k int, digit1 int, digit2 int) int {
	if digit1 == 0 && digit2 == 0 {
		return -1
	}
	digitsMap := map[int]bool{digit1: true, digit2: true}
	digits := []int{}
	for d := range digitsMap {
		digits = append(digits, d)
	}
	queue := []string{}
	visited := map[int]bool{}
	for _, d := range digits {
		if d != 0 {
			queue = append(queue, strconv.Itoa(d))
			visited[d%k] = true
		}
	}
	for len(queue) > 0 {
		numStr := queue[0]
		queue = queue[1:]
		num, _ := strconv.Atoi(numStr)
		rem := num % k
		if rem == 0 && num > k {
			if num > 2147483647 {
				return -1
			}
			return num
		}
		for _, d := range digits {
			newNumStr := numStr + strconv.Itoa(d)
			newRem := (rem*10 + d) % k
			if !visited[newRem] {
				visited[newRem] = true
				queue = append(queue, newNumStr)
			}
		}
	}
	return -1
}

The Go solution mirrors the Python version using slices as queues and maps for visited remainders. Conversion between integers and strings is done explicitly using strconv.

Worked Examples

Example 1: k = 2, digit1 = 0, digit2 = 2

Queue initially: ["2"]

Iteration num_str num rem Action
1 "2" 2 0 2 > 2? No, append "20" and "22"
2 "20" 20 0 20 > 2? Yes, return 20

Output: 20

Example 2: k = 3, digit1 = 4, digit2 = 2

Queue initially: ["2", "4"]

Iteration num_str num rem Action
1 "2" 2 2 append "22", "24"
2 "4" 4 1 append "42", "44"
3 "22" 22 1 append "222", "224"
4 "24" 24 0 24 > 3? Yes, return 24

Output: 24

Example 3: k = 2, digit1 = 0, digit2 = 0

Both digits zero → return -1

Output: -1

Complexity Analysis

Measure Complexity Explanation
Time O(k * 2^D) BFS generates numbers using two digits, modulo k ensures only unique remainders are explored
Space O(k) Stores visited remainders and queue strings, bounded by k

The BFS approach leverages the pigeonhole principle: any number's remainder modulo k can only take k possible values, which ensures the algorithm does not explore infinite paths.

Test Cases

# Provided examples
assert Solution().findInteger(2, 0, 2) == 20  # smallest multiple >2 using 0,2
assert Solution().findInteger(3, 4, 2) == 24  # smallest multiple >3 using 2,4
assert Solution().findInteger(2, 0, 0) == -1  # no digits other than zero

# Additional tests
assert Solution().findInteger(1, 1, 0) == 10   # smallest multiple of 1 >1 with digits 1,0
assert Solution().findInteger(5, 5, 5) == 55   # multiple of 5 >5 with single digit 5
assert Solution().findInteger(7, 1,