Numbers with repeated digits

Math Dynamic Programming

45.8% acceptance

Feb 25, 2026

852

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_dup_digits_at_most_n(n: i32) -> i32 {
    let digits: Vec<i32> = n.to_string().bytes().map(|b| (b-b'0') as i32).collect();
    let len = digits.len();
    fn perm(n: i32, k: i32) -> i32 { if k < 0 { 1 } else { (n-k+1..=n).product() } }
    let mut res = 0;
    for d in 1..len {
      res += 9 * perm(9, (d-1) as i32);
    }
    let mut visited = vec![false; 10];
    for i in 0..len {
      let lo = if i == 0 { 1 } else { 0 };
      let hi = digits[i];
      for d in lo..hi {
        if !visited[d as usize] {
          res += perm(9 - i as i32, (len - i - 1) as i32);
        }
      }
      if visited[digits[i] as usize] { break; }
      visited[digits[i] as usize] = true;
      if i == len - 1 { res += 1; }
    }
    n - res
  }
}