# 233. Number of Digit One

• Time: $O(\log n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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