count the total number of 1's in integers from 1 to N

Question

Problem Statement:

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.

Efficient Solution:

int countDigitOne(int n) {
    if (n <= 0) return 0;
    int q = n, x = 1, ans = 0;
    do {
        int digit = q % 10;
        q /= 10;
        ans += q * x;
        if (digit == 1) ans += n % x + 1;
        if (digit >  1) ans += x;
        x *= 10;
    } while (q > 0);
    return ans;
}

My question:

I found the solution to the question in one of the forums, I am finding it hard to comprehend the solution. I understand its a very simple one but please help me by explaining in detail.

Thank you

Answer 1

So, in the code you included in your question, digit is moving through the digits from right to left and q corresponds with how many xs, an increasing power of ten, are in the number. Each cycle in the while loop counts how many ones are in that position. Let's look at an example:

n     => 131
digit =>  1,  3,  1
q     => 13,  1,  0
x     =>  1, 10,100

q * x      => 13*1
// there are 13 ones in the 10^0 position from 0 to 130 (13 counts of 10)

digit == 1 => n % 1 + 1 = 0 + 1 = 1
// there is 1 one in the 10^0 position from 131 to 131 
   (the remainder for the counts of 10)

---

q * x      => 1*10
// there are 10 ones in the 10^1 position from 0 to 100 (1 count of 100): 10 to 19

digit == 3 => x = 10
// there are 10 ones in the 10^1 position from 101 to 131: 110 to 119
   (the remainder for the counts of 100)

---

q * x      => 0*100
// there are 0 ones in the 10^2 position from 0 to 0 (0 counts of 1000)

digit == 1 => n % 100 + 1 = 31 + 1
// there are 32 ones in the 10^2 position from 0 to 131
   (the remainder for the counts of 1000)

Answer 2

Try to observe the pattern here

Consider N = 2196, which has 4 digits having place values ones, tens, hundreds and thousands.

Now, try to observe the pattern:

Numbers having 1 at ones position
1  11  21  31  41  51  ...

Numbers having 1 at tens position
10  110  210  310  ...
11  111  211  311  ...
......................
19  119  219  319  ...

Numbers having 1 at hundreds position
100  1100  2100  ...
101  1101  2101  ...
102  1102  2102  ...
....................
199  1199  2199  ...

Can you see a cluster of 1 number with a time period of 10 in ones, a cluster of 10 numbers with a time period of 100 in tens and a cluster of 100 numbers with a time period of 1000 in hundreds? So, our final answer would be Summation of (N / Time Period) * Cluster Size But, be careful with the last case, if N % Time Period != 0, There is one more cluster which will not be complete. Try to figure that out by taking N = 2196. From the above analysis:

Here is the C++ code

int solve(int A){
    int ans = 0;
    for(int i = 1; i <= A; i *= 10){
        // i is cluster size.
        // temp is time period.
        int temp = i * 10;
        // min(max(A%temp-i+1, 0), i) -> this part is going to take care 
        // of extra last cluster.
        ans += ((A/temp) * i) + min(max(A%temp-i+1, 0), i);
    }
    return ans;
}