CODEWITHSUNDEEP
algorithmmath
L887
L887

Reputation: 312

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

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

Upvotes: 7

Views: 7870

Answers (3)

Sanjeev Sharma
Sanjeev Sharma

Reputation: 557

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;
}

Upvotes: 5

גלעד ברקן
גלעד ברקן

Reputation: 23955

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)

Upvotes: 4

Adi Levin
Adi Levin

Reputation: 5243

Here is one way to approach this: Suppose that n < 10^k, i.e. n can be represented by k decimal digits. Let's try to construct all positive numbers that have k or less decimal digits, with 1s in them. There are 2^k possibilities to place 1s in some of the k bits.

For each choice of 1 placements, we can easily count all positive numbers that have maximum of k digits, and are smaller than n.

For example, all numbers that match the pattern yxxx1xx11x, where each x can be 0 or 2-9, and y is 2-9. Notice the special y there, because if y==0, the x after it is not allowed to be zero. There are 8 * 9^6 possibilities. So this pattern contributes 3 * 8 * 9^6 to the total count, because each such number contains 3 1's.

This gets a little bit complicated, because we need to restrict the number to those that are smaller or equal to n. This means that not every combination of y and xs are valid. For instance, if n=6239914230, then y<=6, and for y<6, the first x must be at most 2, etc...

Upvotes: 0

Related Questions