233. Number of Digit One
- Math
- Dynamic Programming
- Recursion
TIME
O(log n)
SPACE
O(1)
Intuition
Instead of counting the 1s in each number, count, for each digit position, how many numbers in 0..n have a 1 there. The digit at position p (1, 10, 100, ...) cycles through 0..9, each value held for p consecutive numbers, so every block of 10p numbers has exactly p numbers with a 1 at that position. Only the last, partial block needs care.
Approach
For each position p = 1, 10, 100, ... while p <= n, split n into:
high = n // (10p): the number of complete blocks,cur = (n // p) % 10: the digit at this position,low = n % p: the digits to its right.
Then the count at this position is high * p, plus for the partial block:
cur == 0: nothing, the run of 1s hasn't started yet;cur == 1:low + 1, the numbers from...1000up ton;cur >= 2:p, the whole run of 1s is passed.
Example, n = 13, p = 1: high = 1, cur = 3, giving 1 + 1 = 2 (the 1 and the 11). With p = 10: high = 0, cur = 1, low = 3, giving 4 (10 to 13). Total 6.
Complexity
- Time: O(log n), one step per digit
- Space: O(1)
Edge Cases
n = 0: no positions to process, answer 0nthat is itself a 1 followed by zeros (10,1000):cur == 1,low == 0, so only the number itself counts at the top position- Digits of 0 in the middle (
101): that position adds only the full blocks n = 10^9: in Java,pwould step from10^9to10^10and overflowint, sopis along
Code
class Solution:
def countDigitOne(self, n: int) -> int:
"""
233. Number of Digit One
Time: O(log n)
Space: O(1)
"""
count = 0
p = 1
while p <= n:
high, cur, low = n // (p * 10), (n // p) % 10, n % p
# Each full block of 10p numbers has p ones at this position.
count += high * p
# The partial block: before, inside, or past the run of 1s.
if cur == 1:
count += low + 1
elif cur > 1:
count += p
p *= 10
return count/**
* 233. Number of Digit One
* Time: O(log n)
* Space: O(1)
*/
class Solution {
public int countDigitOne(int n) {
long count = 0;
// long: p reaches 10^10 after the last digit of n = 10^9.
for (long p = 1; p <= n; p *= 10) {
long high = n / (p * 10), cur = (n / p) % 10, low = n % p;
// Each full block of 10p numbers has p ones at this position.
count += high * p;
// The partial block: before, inside, or past the run of 1s.
if (cur == 1) {
count += low + 1;
} else if (cur > 1) {
count += p;
}
}
return (int) count;
}
}