## Number of Digit One

• Time:O(\log n)
• Space:O(1)

## C++

``````class Solution {
public:
int countDigitOne(int n) {
int ans = 0;

for (long pow10 = 1; pow10 <= n; pow10 *= 10) {
const long divisor = pow10 * 10;
const int quotient = n / divisor;
const int remainder = n % divisor;
if (quotient > 0)
ans += quotient * pow10;
if (remainder >= pow10)
ans += min(remainder - pow10 + 1, pow10);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int countDigitOne(int n) {
int ans = 0;

for (long pow10 = 1; pow10 <= n; pow10 *= 10) {
final long divisor = pow10 * 10;
final int quotient = (int) (n / divisor);
final int remainder = (int) (n % divisor);
if (quotient > 0)
ans += quotient * pow10;
if (remainder >= pow10)
ans += Math.min(remainder - pow10 + 1, pow10);
}

return ans;
}
}
``````

## Python

``````class Solution:
def countDigitOne(self, n: int) -> int:
ans = 0

pow10 = 1
while pow10 <= n:
divisor = pow10 * 10
quotient = n // divisor
remainder = n % divisor
if quotient > 0:
ans += quotient * pow10
if remainder >= pow10:
ans += min(remainder - pow10 + 1, pow10)
pow10 *= 10

return ans
``````