233. Number of Digit One

At a Glance

Topic: math-geometry
Pattern: Digit / positional counting + Dynamic Programming — digit DP (constructive closed form here)
Difficulty: Hard
Companies: Google, Amazon, Bloomberg, Rubrik, LinkedIn
Frequency: Low
LeetCode: 233

Problem (one-liner)

Given integer n >= 0, count how many times digit 1 appears in the decimal representation of all integers from 0 to n inclusive.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Count digit d over range [0, n] — treat each decimal position independently
Avoid iterating 0..n when n is large
Classic high / current / low decomposition per factor = 1, 10, 100, ...

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute stringify each number — O(n log n) — fails scale.
Per-position formula — O(log n) digits — optimal.
Digit DP — same complexity, more machinery — good when bounds vary.

Optimal Solution

Go

func countDigitOne(n int) int {
	if n <= 0 {
		return 0
	}
	count := 0
	for factor := 1; factor <= n; factor *= 10 {
		divider := factor * 10
		higher := n / divider
		current := (n / factor) % 10
		lower := n % factor
		if current == 0 {
			count += higher * factor
		} else if current == 1 {
			// ones from higher block plus partial lower tail
			count += higher*factor + lower + 1
		} else {
			count += (higher + 1) * factor
		}
	}
	return count
}

JavaScript

function countDigitOne(n) {
  if (n <= 0) {
    return 0;
  }
  let count = 0;
  for (let factor = 1; factor <= n; factor *= 10) {
    const divider = factor * 10;
    const higher = Math.floor(n / divider);
    const current = Math.floor(n / factor) % 10;
    const lower = n % factor;
    if (current === 0) {
      count += higher * factor;
    } else if (current === 1) {
      count += higher * factor + lower + 1;
    } else {
      count += (higher + 1) * factor;
    }
  }
  return count;
}

Walkthrough

At factor=10 for n=314159, split into higher block count of full 10-wide bands of ones in tens place, plus partial when current digit is 0/1/>1.

Invariant: Summing each position’s contribution counts every integer’s 1s exactly once.

Edge Cases

n = 0 — zero ones
Powers of ten boundaries — verify current == 1 branch
Negative n — not in problem constraints

Pitfalls

factor overflow — use int64 for products if language needs on huge n
Miscounting leading zeros — formula accounts only positional weights

Variants

Count digit d in [0,n] — same skeleton, adjust branches when current == d
Range [low, high] — count(high) - count(low-1)
Binary representation — count 1 bits in sequence — unrelated simpler bit DP

Mind-Map Tags

#digit-dp #positional-count #high-current-low #range-aggregate #math-trick