In this guide, you will get 233. Number of Digit One LeetCode Solution with the best time and space complexity. The solution to Number of Digit One problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example 1:
Input: n = 13
Output: 6
Example 2:
Input: n = 0
Output: 0
Constraints:
0 <= n <= 109
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(1)
233. Number of Digit One LeetCode Solution in 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;
}
};
/* code provided by PROGIEZ */
233. Number of Digit One LeetCode Solution in 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;
}
}
// code provided by PROGIEZ
233. Number of Digit One LeetCode Solution in 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
# code by PROGIEZ
