Numbers at most n given digit set

Array Math String Binary Search Dynamic Programming

44.6% acceptance

Feb 25, 2026

1465

Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'. Return the number of positive integers that can be generated that are less than or equal to a given integer n.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn at_most_n_given_digit_set(digits: Vec<String>, n: i32) -> i32 {
    let s = n.to_string();
    let d_chars: Vec<char> = digits.iter().map(|x| x.chars().next().unwrap()).collect();
    let m = s.len();
    let d = d_chars.len();
    let mut res = 0i32;
    // Count numbers with fewer digits
    let mut pow = 1i32;
    for _ in 1..m { pow *= d as i32; res += pow; }
    // Count m-digit numbers <= n
    for i in 0..m {
      let ni = s.chars().nth(i).unwrap();
      let cnt = d_chars.iter().filter(|&&c| c < ni).count() as i32;
      let remaining = (m - i - 1) as u32;
      res += cnt * (d as i32).pow(remaining);
      if !d_chars.contains(&ni) { break; }
      if i == m - 1 { res += 1; }
    }
    res
  }
}