233. Number of Digit One
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
- 0 <= n <= $2 * 10^9$
4. Solutions
My Accepted Solution
Time complexity: O($log_{10}n$)
Space complexity: O(1)
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;
}
};