Skip to main content
Back to problems
#233
Hard Algorithms

Number of digit one

Math Dynamic Programming Recursion
37.7% acceptance
Jan 12, 2026
1820
1554
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs
impl Solution {
  pub fn count_digit_one(n: i32) -> i32 {
    let mut count = 0;
    let mut factor = 1i64;
    let n = n as i64;
    
    while factor <= n {
      let higher = n / (factor * 10);
      let cur = (n / factor) % 10;
      let lower = n % factor;
      
      if cur == 0 {
        count += higher * factor;
      } else if cur == 1 {
        count += higher * factor + lower + 1;
      } else {
        count += (higher + 1) * factor;
      }
      factor *= 10;
    }
    count as i32
  }
}