Smallest greater multiple made of two digits

Math Enumeration

48.1% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::VecDeque;

impl Solution {
  pub fn find_integer(k: i32, digit1: i32, digit2: i32) -> i32 {
    // BFS over numbers made of digit1 and digit2
    // We generate numbers in increasing order using BFS
    let d1 = digit1.min(digit2);
    let d2 = digit1.max(digit2);
    
    if d1 == 0 && d2 == 0 {
      return -1;
    }
    
    let mut queue: VecDeque<i64> = VecDeque::new();
    // Start with non-zero digits
    if d1 > 0 { queue.push_back(d1 as i64); }
    if d2 > 0 && d2 != d1 { queue.push_back(d2 as i64); }
    
    let limit = i32::MAX as i64;
    
    while let Some(num) = queue.pop_front() {
      if num > limit {
        return -1;
      }
      if num > k as i64 && num % k as i64 == 0 {
        return num as i32;
      }
      let n1 = num * 10 + d1 as i64;
      let n2 = num * 10 + d2 as i64;
      if n1 <= limit {
        queue.push_back(n1);
      }
      if d1 != d2 && n2 <= limit {
        queue.push_back(n2);
      }
    }
    -1
  }
}