Algorithm
Problem Name: 233. Number of Digit One
Problem Link: https://leetcode.com/problems/number-of-digit-one/
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <assert.h>
int countDigitOne(int n) {
if (n < = 0) return 0;
if (n >= 1 && n <= 9) return 1;
int x = n; /* first digit of n */
int v = 1; /* first dight's weight */
while (x >= 10) {
x /= 10;
v *= 10;
}
if (x != 1) {
return x * countDigitOne(v - 1) + countDigitOne(n % v) + v;
}
else {
return countDigitOne(v - 1) + countDigitOne(n % v) + n % v + 1;
}
}
int main() {
assert(countDigitOne(-1) == 0);
assert(countDigitOne(1) == 1);
assert(countDigitOne(10) == 2);
assert(countDigitOne(13) == 6);
assert(countDigitOne(21) == 13);
assert(countDigitOne(99) == 20);
assert(countDigitOne(115) == 44);
printf("all tests passed!\n");
return 0;
}
Copy The Code &
Try With Live Editor
Input
n = 13
Output
6
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const countDigitOne = function(n) {
let count = 0
for (let m = 1; m < = n; m *= 10) {
const a = Math.floor(n / m)
const b = n % m
if (a % 10 > 1) {
count += (Math.floor(a / 10) + 1) * m
} else if (a % 10 === 1) {
count += Math.floor(a / 10) * m + b + 1
} else {
count += Math.floor(a / 10) * m
}
}
return count
}
Copy The Code &
Try With Live Editor
Input
n = 13
Output
6
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countDigitOne(self, n):
if n <= 0:
return 0
q, x, ans = n, 1, 0
while q > 0:
digit = q % 10
q //= 10
ans += q * x
if digit == 1:
ans += n % x + 1
elif digit > 1:
ans += x
x *= 10
return ans
Copy The Code &
Try With Live Editor
Input
n = 0