1. Description
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
2. Example
Example 1
Input: n = 13
Output: 6
Example 2
Input: n = 0
Output: 0
3. Note
4. Solutions
Math
Time complexity: O($log_{10}n$)
Space complexity: O(1)
1～n 整数中 1 出现的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution
{
public:
int countDigitOne(int n)
{
int digitOneCount = 0;
for(long base = 1; base <= n; base *= 10)
{
long divider = base * 10;
int leftOneDigit = n / divider * base;
int basePositionNumber = n % divider;
int currentOneDigit = (basePositionNumber < base ? 0 : min(base, basePositionNumber - base + 1));
digitOneCount += leftOneDigit + currentOneDigit;
}
return digitOneCount;
}
};
|