Leetcode 233. Number of Digit One

Problem Explanation:

Given an integer n, we need to count the total number of digit 1 that appears in all non-negative integers less than or equal to n. For example, if we have n = 13, the numbers less than or equal to 13 are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. The digit '1' appears 6 times in these numbers (1, 10, 11(contains '1' twice), 12, 13).

The approach to solve this problem is to count the appearances of the digit 1 in every place from low to high(in decimal notation).

For example, if we have n = 3141592, and we are currently considering the hundreds place:

There are 31415 hundreds in total. For the first 3141 hundreds, there is one '1' in every hundred(like 100 to 199, 1100 to 1199, etc.).

For the 3142nd hundred, since it's 4200, there isn't a hundred with '1'. So the total number of '1's in the hundreds place should be 3141 * 100 + 41. (For the first 3141 hundreds, each hundred contributes 100 '1's, and for the 3142nd hundred, it contributes 41 '1's.)

By iterating the place from low to high, we can get the total number of '1's from 1 to n.

Solution:

Python

In python, the solution is quite similar to the explanation above.

1
2python
3class Solution:
4    def countDigitOne(self, n: int) -> int:
5        ans = 0
6        multiplier = 1
7        while n >= multiplier:
8            ans += (n // (multiplier * 10)) * multiplier + min(max(n % (multiplier * 10) - multiplier + 1, 0), multiplier)
9            multiplier *= 10
10        return ans

Java

A java solution can be implemented likewise.

1
2java
3class Solution {
4    public int countDigitOne(int n) {
5        int ans = 0;
6        for (long pow10 = 1; pow10 <= n; pow10 *= 10) {
7            long divisor = pow10 * 10;
8            ans += (n / divisor) * pow10 + Math.min(Math.max(n % divisor - pow10 + 1, 0), pow10);
9        }
10        return ans;
11    }
12}

JavaScript

JavaScript solution can be implemented as follows:

1
2javascript
3var countDigitOne = function(n) {
4    let ans = 0, multiplier = 1;
5
6    while (n >= multiplier) {
7        ans += Math.floor(n / (10 * multiplier)) * multiplier + Math.min(Math.max(n % (10 * multiplier) - multiplier + 1, 0), multiplier);
8        multiplier *= 10;
9    }
10    return ans;
11};

C++

A C++ solution can be implemented likewise.

1
2c++
3class Solution {
4public:
5    int countDigitOne(int n) {
6      int ans = 0;
7
8      for (long pow10 = 1; pow10 <= n; pow10 *= 10) {
9          long divisor = pow10 * 10;
10          ans += (n / divisor) * pow10 + min(max(n % divisor - pow10 + 1, 0L), pow10);
11      }
12
13      return ans;
14    }
15};

C#

A C# solution can be implemented as follows:

1
2csharp
3public class Solution {
4    public int CountDigitOne(int n) {
5        int ans = 0;
6        for (long m = 1; m <= n; m *= 10)
7            ans += (n/m + 8) / 10 * m + (n/m % 10 == 1 ? n%m + 1 : 0);
8        return ans;
9    }
10}

These solutions are functioning based on the same logic as explained earlier. They first count the appearances of '1' in every place from low to high, and then sum them up.

The final return statement gives the total number of digit 1 that appears in all non-negative integers less than or equal to n.

That's it! Now you can count the number of '1's in every place from low to high in a given number using Python, Java, JavaScript, C++ and C#. Applying this concept in a problem-solving scenario would require logical thinking and understanding of the underlying mathematics.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫