Digit count in range

Math Dynamic Programming

46.5% acceptance

Mar 31, 2026

Given a single-digit integer d and two integers low and high, return the number of times that d occurs as a digit in all integers in the inclusive range [low, high].

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn digits_count(d: i32, low: i32, high: i32) -> i32 {
    fn count(n: i64, d: i64) -> i64 {
      let mut result = 0i64;
      let mut multiplier = 1i64;
      while multiplier <= n {
        let lower = n % multiplier;
        let current = (n / multiplier) % 10;
        let higher = n / (multiplier * 10);
        result += match current.cmp(&d) {
          std::cmp::Ordering::Greater => (higher + 1) * multiplier,
          std::cmp::Ordering::Equal => higher * multiplier + lower + 1,
          std::cmp::Ordering::Less => higher * multiplier,
        };
        if d == 0 {
          result -= multiplier;
        }
        multiplier *= 10;
      }
      result
    }
    let d = d as i64;
    (count(high as i64, d) - count(low as i64 - 1, d)) as i32
  }
}