DSA problem
Number of Digit One
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example, with n = 13, the integers 1, 10, 11, 12, 13 contain six 1 digits in total (1 in 1, 1 in 10, two in 11, 1 in 12, 1 in 13).
A naive approach iterates every integer from 1 to n and counts ones in its decimal expansion. That costs O(n log n) time, which is far too slow when n can be as large as 2 * 10^9. The structural insight that makes this efficient is to count, for each decimal position independently, how many times a 1 lands at that position across the entire range [1, n], and then sum those positional contributions.
Fix a position i corresponding to the place value i = 10^p (units, tens, hundreds, ...). Split n into three parts at that position: high = n / (i * 10) (the digits to the left of position i), cur = (n / i) % 10 (the digit currently at position i), and low = n % i (the digits to the right). Each full cycle of the wheel at position i produces exactly i numbers with a 1 at that position, and high complete cycles have already passed.
The contribution of position i depends on cur. If cur == 0, the position has only completed cycles, so it contributes high * i. If cur == 1, completed cycles plus the partial current cycle contribute high * i + low + 1. If cur >= 2, the current cycle has already passed its 1-range entirely, so it adds one more full block: (high + 1) * i. Summing these contributions across every i = 1, 10, 100, ... until i > n gives the answer in O(log10 n) time with O(1) space.
Examples
n = 136n = 00n = 2012Constraints
- 0 <= n <= 2 * 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.