#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)
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
}
}