leetcode Question: Number of Digit One

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.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Analysis:

It takes me a couple of hours to figure out a easy way to solve this problem. Basically once you get the idea, it would take you less than 10 mins to implement the code, and before that, all you need is a piece of paper and a pencil.

At the first glance, what usually comes up to our mind is different O(n) solutions, however this won't pass the OJ. We must think from another way: from digit to digit.

Lets' first take a look at an easier problem:  how many digits 1 appearing in all non-negative integers less than or equal to n-digits length integer?  In other words, how many "1"s in  0-9 (1-digit), how many "1"s in 0-99, how many "1"s in 0-999...

From 0-9, it is not hard to find out there is only 1 "1" (here "1" indicates the digit 1 in integer), it occurred in integer 1.

From 0-99, counting number of "1" is a procedure as follows:
1. Consider two blank slots which we fill number in them: [ ][ ]

2. Both digits are ranging from 0-9, e.g., [0][2] = 2, [1][3] = 13, denote as [0-9][0-9].

3. There are two cases:  [0,2-9][ 0-9] and [1][0-9]

4. Case 1: [0,2-9][0-9]. There is no "1" in the highest digit. "1" only appears in the rest of digits, here is one digit [0-9]. For each number in [0, 2-9], we have the number of "1" from its lower digit(s) [0-9], which is 1. Now we have 10 different possible highest digits, i.e., 0,2,3,4,5,6,7,8,9, for every one of them, the lower digit(s) can generate 1 "1", in total there are 10 *1 = 10  "1"s in this case.

5. Case 2: [1][0-9]. "1" is in highest digit, which means every possible number in  its lower digits (now is [0-9]) contains one "1".  So there are 1*10  = 10 "1"s in this case.

6. Sum Case 1 and Case 2 up, we have 20 "1"s from 0-99.



Next, let's see how to count "1" from 0-999, similar to previous steps:
1. We have three blank slots [ ][ ][ ].

2. There are two cases: [1][0-9][0-9] , and [0, 2-9][0-9][0-9].

3. Case 1:  [0, 2-9][0-9][0-9]. # of "1" is in this case equal to:  # of "1" in [0-9][0-9]  times 10 =  20*10 = 200.

4. Case 2: [1][0-9][0-9], we have more "1"s since all numbers in form [1][0][0] to [1][9][9] have an additional "1" in their highest digit. Thus, we need to add 100, which is # of integers from 100-199.

5. The total number of "1" from 0-999 is 300.




Getting clear the above procedures, now we are targeting arbitrary number. Let's take an example,
say n = 5746. Denote function C(m,n) as the number of digit "1" appearing from integer m to integer n. We can write down the procedure:

$$
\small\begin{array}{ccccccccccccc}
C(0,5746) & = & C(0,999) & + & C(1000,5746)\\
& = & C(0,999) & + & 4*C(0,999) & + & 1000 & + & C(5000,5746)\\
& = & 5*C(0,999) & + & 1000 & + & C(0,746)\\
& = & 5*C(0,999) & + & 1000 & + & C(0,99) & + & C(100,746)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & C(700,746)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & 100 & + & C(0,46)\\
& = & 5*C(0,999) & + & 1000 & + & 7*C(0,99) & + & 100 & + & 5*C(0,9) & + & 10\\
& = & 5*300 & + & 1000 & + & 7*20 & + & 100 & + & 5 & + & 10\\
& = & 2755

\end{array}
$$


Although it looks complicated, from the programming view, it is much easier. There are two cases you have to pay attention to, (1). When current digit is 0, there no additional "1" to be added. (1000, and 100 and 10 in the above expression.) (2) When current digit is 1, the additional "1" is not 10,100,or 1000 any more, but the actual number in its lower digits.

In my implementation, I choose to use lower to higher order rather than the higher to lower order when scanning each digit. To get i-th digit, we can use \((n\%10^{i})/(i/10)\). I use bool type to check the current digit to simplify my code.  "m" indicates the number of "1"s  in 0-9, 0-99, 0-999 and so on.

Code(C++):

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        int m = 0;
        for (long i=1;i<=n;i=i*10){
            int d = n%(i*10)/i;
            res += d*m + (d == 1)*(n%i + 1) + (d>1)*(i);
            m = m*10 +i;
        }
        return res;
    }
};

Code(Python):

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        m = 0
        i = 1
        while i <= n:
            d = n%(i*10)/i;
            res += d*m + (d == 1)*(n%i + 1) + (d>1)*i
            m = m*10 +i
            i = i*10
        return res