LeetCode 233: Number of Digit One (Place-Value Counting)
LeetCode 233MathDigit CountingToday we solve LeetCode 233 - Number of Digit One.
Source: https://leetcode.com/problems/number-of-digit-one/
English
Problem Summary
Given an integer n, count how many times digit 1 appears in all non-negative integers from 0 to n.
Key Insight
Count digit 1 contribution independently at each decimal place m = 1, 10, 100, .... For a fixed place, split n into three parts:
high = n / (m * 10), cur = (n / m) % 10, low = n % m.
Then the count contributed by this place is:
- If cur == 0: high * m
- If cur == 1: high * m + low + 1
- If cur >= 2: (high + 1) * m
Brute Force and Why We Improve
A brute force method scans every number from 1..n and counts ones digit-by-digit, which costs roughly O(n log n). For large n, this is too slow. Place-value counting finishes in O(log n).
Optimal Algorithm (Step-by-Step)
1) Initialize ans = 0, m = 1.
2) While m <= n, compute high, cur, low for this place.
3) Apply the three-case formula to add contribution into ans.
4) Multiply m by 10 and continue.
5) Return ans.
Complexity Analysis
Time: O(log10 n).
Space: O(1).
Common Pitfalls
- Integer overflow when computing m * 10 (use long/long long).
- Forgetting the + low + 1 part when cur == 1.
- Off-by-one errors from mixing range 0..n with 1..n; this formula already handles it correctly.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int countDigitOne(int n) {
long ans = 0;
for (long m = 1; m <= n; m *= 10) {
long high = n / (m * 10);
long cur = (n / m) % 10;
long low = n % m;
if (cur == 0) {
ans += high * m;
} else if (cur == 1) {
ans += high * m + low + 1;
} else {
ans += (high + 1) * m;
}
}
return (int) ans;
}
}func countDigitOne(n int) int {
var ans int64 = 0
nn := int64(n)
for m := int64(1); m <= nn; m *= 10 {
high := nn / (m * 10)
cur := (nn / m) % 10
low := nn % m
if cur == 0 {
ans += high * m
} else if cur == 1 {
ans += high*m + low + 1
} else {
ans += (high + 1) * m
}
}
return int(ans)
}class Solution {
public:
int countDigitOne(int n) {
long long ans = 0;
for (long long m = 1; m <= n; m *= 10) {
long long high = n / (m * 10);
long long cur = (n / m) % 10;
long long low = n % m;
if (cur == 0) {
ans += high * m;
} else if (cur == 1) {
ans += high * m + low + 1;
} else {
ans += (high + 1) * m;
}
}
return (int)ans;
}
};class Solution:
def countDigitOne(self, n: int) -> int:
ans = 0
m = 1
while m <= n:
high = n // (m * 10)
cur = (n // m) % 10
low = n % m
if cur == 0:
ans += high * m
elif cur == 1:
ans += high * m + low + 1
else:
ans += (high + 1) * m
m *= 10
return ansvar countDigitOne = function(n) {
let ans = 0n;
const nn = BigInt(n);
for (let m = 1n; m <= nn; m *= 10n) {
const high = nn / (m * 10n);
const cur = (nn / m) % 10n;
const low = nn % m;
if (cur === 0n) {
ans += high * m;
} else if (cur === 1n) {
ans += high * m + low + 1n;
} else {
ans += (high + 1n) * m;
}
}
return Number(ans);
};中文
题目概述
给定整数 n，统计从 0 到 n 的所有数字中，数字 1 一共出现了多少次。
核心思路
按十进制位拆分统计。对每一位 m = 1, 10, 100, ...，把 n 分成三段：
high = n / (m * 10)，cur = (n / m) % 10，low = n % m。
该位贡献分三种情况：
- cur == 0：贡献 high * m
- cur == 1：贡献 high * m + low + 1
- cur >= 2：贡献 (high + 1) * m
朴素解法与优化
朴素法是从 1..n 每个数逐位统计 1 的个数，复杂度约 O(n log n)。按位计数只需遍历位数，复杂度降到 O(log n)。
最优算法（步骤）
1）初始化 ans = 0，m = 1。
2）当 m <= n 时，计算该位的 high、cur、low。
3）根据 cur 属于 0/1/>=2 三种情况累加贡献。
4）令 m *= 10，继续处理下一位。
5）返回 ans。
复杂度分析
时间复杂度：O(log10 n)。
空间复杂度：O(1)。
常见陷阱
- 计算 m * 10 时整型溢出（建议使用 long/long long）。
- cur == 1 时漏加 low + 1。
- 范围边界处理混乱；该公式天然适配从 0..n 的统计。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int countDigitOne(int n) {
long ans = 0;
for (long m = 1; m <= n; m *= 10) {
long high = n / (m * 10);
long cur = (n / m) % 10;
long low = n % m;
if (cur == 0) {
ans += high * m;
} else if (cur == 1) {
ans += high * m + low + 1;
} else {
ans += (high + 1) * m;
}
}
return (int) ans;
}
}func countDigitOne(n int) int {
var ans int64 = 0
nn := int64(n)
for m := int64(1); m <= nn; m *= 10 {
high := nn / (m * 10)
cur := (nn / m) % 10
low := nn % m
if cur == 0 {
ans += high * m
} else if cur == 1 {
ans += high*m + low + 1
} else {
ans += (high + 1) * m
}
}
return int(ans)
}class Solution {
public:
int countDigitOne(int n) {
long long ans = 0;
for (long long m = 1; m <= n; m *= 10) {
long long high = n / (m * 10);
long long cur = (n / m) % 10;
long long low = n % m;
if (cur == 0) {
ans += high * m;
} else if (cur == 1) {
ans += high * m + low + 1;
} else {
ans += (high + 1) * m;
}
}
return (int)ans;
}
};class Solution:
def countDigitOne(self, n: int) -> int:
ans = 0
m = 1
while m <= n:
high = n // (m * 10)
cur = (n // m) % 10
low = n % m
if cur == 0:
ans += high * m
elif cur == 1:
ans += high * m + low + 1
else:
ans += (high + 1) * m
m *= 10
return ansvar countDigitOne = function(n) {
let ans = 0n;
const nn = BigInt(n);
for (let m = 1n; m <= nn; m *= 10n) {
const high = nn / (m * 10n);
const cur = (nn / m) % 10n;
const low = nn % m;
if (cur === 0n) {
ans += high * m;
} else if (cur === 1n) {
ans += high * m + low + 1n;
} else {
ans += (high + 1n) * m;
}
}
return Number(ans);
};
Comments