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

x
+
cmd
n = 13

Output

x
+
cmd
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

x
+
cmd
n = 13

Output

x
+
cmd
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

x
+
cmd
n = 0
Advertisements

Demonstration


Previous
#232 Leetcode Implement Queue using Stacks Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#234 Leetcode Palindrome Linked List Solution in C, C++, Java, JavaScript, Python, C# Leetcode