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.

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, ...

Diagram

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

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

Similar Problems

• 50. Pow(x, n) — digit / halving structure (Medium stepping stone)
• 43. Multiply Strings — digit-wise arithmetic (Medium)
• 149. Max Points on a Line — exact rational / counting (Hard)

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