Number of Digit One
Hard · Math · Math · Dynamic Programming · Recursion
Problem
Given an integer n, count how many times the digit 1 appears in total when every integer from 0 to n is written out in decimal.
A number with several 1s counts each of them: 11 contributes two.
n can be as large as a billion, so going number by number is too slow. Count place by place instead.
Examples
Input: n = 12 Output: 5
1, 10 and 12 have one 1 each, and 11 has two: 5 in all.
Input: n = 0 Output: 0
Only the number 0, which has no 1.
Input: n = 100 Output: 21
Ten in the ones place (1, 11, ..., 91), ten in the tens place (10..19) and one in 100: 21.
Constraints
- 0 <= n <= 10^9
Approaches
- Count digit by digit in every number — time O(n log n), space O(1)
Follow-up
The place-by-place count works for any nonzero digit d by comparing cur with d instead of 1 (the first use case). The digit 0 needs care because numbers have no leading zeros. Counting numbers that contain a 1, rather than the 1s themselves, needs a different count: the second use case counts the numbers that avoid 1 and subtracts.
Related problems
Start free on Cariara · Coding problems · System design studio
