Count special integers

Math Dynamic Programming

41.8% acceptance

Feb 25, 2026

628

We call a positive integer special if all of its digits are distinct. Given a positive integer n, return the number of special integers that belong to the interval [1, n].

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_special_numbers(n: i32) -> i32 {
    let s: Vec<u32> = n.to_string().chars().map(|c| c.to_digit(10).unwrap()).collect();
    let len = s.len();
    let perm = |m: i32, k: usize| -> i32 { (0..k as i32).fold(1, |acc, i| acc * (m - i)) };
    let mut count = 0i32;
    // Count d-digit specials for d < len
    for d in 1..len {
      count += if d == 1 { 9 } else { 9 * perm(9, d - 1) };
    }
    // Count len-digit specials <= n
    let mut used = [false; 10];
    for (i, &d) in s.iter().enumerate() {
      let count_smaller = if i == 0 {
        d as i32 - 1 // digits 1..d-1
      } else {
        (0..d).filter(|&x| !used[x as usize]).count() as i32
      };
      count += count_smaller * perm(10 - (i as i32) - 1, len - i - 1);
      if used[d as usize] { break; }
      used[d as usize] = true;
      if i == len - 1 { count += 1; }
    }
    count
  }
}