Number of Digit One
Problem
n, write out every integer from
0 to n and return how many times the digit 1
appears in total (so 11 contributes two).n=21Output13 (1, 10, 11×2, 12..19, 21)n=0Output0n=2131Output16660 ≤ n ≤ 109
Try it yourself
class Solution {
public int countDigitOne(int n) {
}
}
p, split
n into high, cur, low: the column shows
a 1 exactly high·p times, plus low+1 more if
cur == 1, or plus a full p if cur > 1.Instinct Count numbers in [L, R] (R up to 10^9 or 10^18) whose digits obey a rule - build the number digit by digit with a "still tight to N" flag.
Memory hack Walk the digits on a leash - stay tight to N or break free, and once free you never go back. Remember PTLS - Position, Tight, Leading zero, State.
Open the Digit DP guide →Approaches
Brute ForceCount Ones in Every Number
O(n log n)Space O(1)Walk x from 1 to n and strip its digits with
% 10, adding one for each digit equal to 1.
public int countDigitOne(int n) { int total = 0; for (int x = 1; x <= n; x++) for (int y = x; y > 0; y /= 10) if (y % 10 == 1) total++; return total; }
Fine for checking answers; ~1010 digit operations at n = 109.
BetterDigit DP with a Tight Flag
O(10 · L²)Space O(L²)Fill the digits of numbers ≤ n from left to right, tracking how
many 1s were placed and whether the prefix still equals n's prefix
(tight). Once a prefix is below n, the rest is free, so the result depends
only on (pos, ones) and is memoised. L = digit count.
private char[] digits; private int[][] memo; // memo[pos][ones] for non-tight prefixes public int countDigitOne(int n) { digits = String.valueOf(n).toCharArray(); memo = new int[digits.length][digits.length + 1]; for (int[] row : memo) Arrays.fill(row, -1); return count(0, 0, true); } // total 1s over all numbers that extend the current prefix private int count(int pos, int ones, boolean tight) { if (pos == digits.length) return ones; if (!tight && memo[pos][ones] >= 0) return memo[pos][ones]; int limit = tight ? digits[pos] - '0' : 9; int total = 0; for (int d = 0; d <= limit; d++) total += count(pos + 1, ones + (d == 1 ? 1 : 0), tight && d == limit); if (!tight) memo[pos][ones] = total; return total; }
Logarithmic and a reusable template for any “digits of numbers ≤ n” count.
OptimalPer-Position Formula
O(log n)Space O(1)For each place value p = 1, 10, 100, … the column cycles
through 0–9, each digit lasting p numbers. The
high full cycles give high·p ones; the partial cycle
adds nothing (cur = 0), low+1 (cur = 1) or a
full p (cur ≥ 2).
public int countDigitOne(int n) { long count = 0; for (long p = 1; p <= n; p *= 10) { // long: p * 10 would overflow int long high = n / (p * 10); long cur = (n / p) % 10; long low = n % p; if (cur == 0) count += high * p; else if (cur == 1) count += high * p + low + 1; else count += (high + 1) * p; } return (int) count; }
Dry runn=21
- p=12131chi=213 lo=0: +214
- p=10213c1hi=21 cur=3: +220 = 434
- p=10021c31hi=2 lo=31: +232 = 666
- p=10002c131hi=0 cur=2: +1000 ✔
Closed form per digit — at most 10 iterations for any valid n.
low + 1.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Count Ones in Every Number | O(n log n) | O(1) |
| Better | Digit DP with a Tight Flag | O(10 · L²) | O(L²) |
| Optimal | Per-Position Formula | O(log n) | O(1) |
- Using
intforp:p * 10overflows when n is near 109. - Forgetting the
+1inlow + 1(the number with all-zero low part counts too). - Memoising tight states in the digit DP — they depend on n's suffix, not just
(pos, ones).
- Write out 0..25 and count ones per column to discover the pattern together.
- Present the three cases (cur = 0, 1, ≥ 2) as a small table.
- Mention digit DP as the general tool when the per-digit rule is more complex.