Skip to main content
Back to problems
#3747
Medium Algorithms

Count distinct integers after removing zeros

Math Dynamic Programming
22.4% acceptance
Feb 25, 2026
117
10
You are given a positive integer n. For every integer x from 1 to n, we write down the integer obtained by removing all zeros from the decimal representation of x. Return an integer denoting the number of distinct integers written down.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn count_distinct(n: i64) -> i64 {
    let s: Vec<u8> = n.to_string().bytes().map(|b| b - b'0').collect();
    let len = s.len();
    let mut result = 0i64;
    // d-digit zero-free numbers: 9^d each, for d < len
    for d in 1..len {
      result += 9i64.pow(d as u32);
    }
    // d-digit zero-free numbers <= n (tight DP)
    let mut valid = true;
    for i in 0..len {
      let d = s[i];
      let free = (len - i - 1) as u32;
      if d >= 1 {
        result += (d as i64 - 1) * 9i64.pow(free);
      }
      if d == 0 { valid = false; break; }
    }
    if valid { result += 1; }
    result
  }
}