Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

233. Number of Digit One

Time: $O(\log n)$

Space: $O(1)$

			


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;
  }
};




			


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;
  }
}




			


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