Count the number of Ks between 0 and N

Question

Problem:

I have seen questions like:

1. count the number of 0s between 0 and N?
2. count the number of 1s between 0 and N?
3. count the number of 2s between 0 and N?
4. ... ...

These kinds of questions are very similar of asking to find the total number that Ks (i.e. K=0,1,2,...,9) are shown in number range [0, N].

Example:

• Input: K=2, N=35
• Output: 14
• Detail: list of 2s between [0,35]: 2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32, note that 22 will be counted as twice (as 22 contains two 2s)

---

What we have:

There are solutions for each of them (available if you search for it). Usually, O(log N) time is needed to solve such questions by recursively taking the highest digit into consideration, and so on. One example of counting the number of 2s between 0 and N can be solved by the following procedure (borrowed from here):

// Take n = 319 as example => 162
int numberOf2sBetween0AndN(int n) 
{
    if (n < 2)
        return 0;

    int result = 0;
    int power10 = 1;
    while (power10 * 10 < n)
        power10 *= 10;

    // power10 = 100
    int msb = n / power10; // 3
    int reminder = n % power10; // 19

    /*** Count # of 2s from MSB ***/
    if (msb > 2)    // This counts the first 2 from 200 to 299
        result += power10;
    if (msb == 2)   // If n = 219, this counts the first 2 from 200 to 219 (20 of 2s).
        result += reminder + 1;

    /*** Count # of 2s from reminder ***/
    // This (recursively) counts for # of 2s from 1 to 100; msb = 3, so we need to multiply by that.
    result += msb * numberOf2s(power10);
    // This (recursively) counts for # of 2s from 1 to reminder
    result += numberOf2s(reminder);

    return result;
}

---

Question:

Note that, we cannot simply change all 2s part in the above code to 1s in order to solve the problem of counting the number of 1s between 0 and N. It seems that we have to handle differently (not trivial) for different cases.

Is there a general procedure we can follow to handle all Ks (i.e. K=0,1,2,...,9), i.e. something like the following function?

int numberOfKsBetween0AndN(int k, int n) 

---

Test cases:

Here are some test cases if you want to check your solution:

• k=1, N=1: 1
• k=1, N=5: 1
• k=1, N=10: 2
• k=1, N=55: 16
• k=1, N=99: 20
• k=1, N=10000: 4001
• k=1, N=21345: 18821
• k=2, N=10: 1
• k=2, N=100: 20
• k=2, N=1000: 300
• k=2, N=2000: 601
• k=2, N=2145: 781
• k=2, N=3000: 1900

Answer 1

It can be done arithmetically.

EDIT

I didn't see your code example at first. My code is very similar, except inputs are parametrized. So the answer is Yes, it can be generalized, but you need to handle 0 as special case.

If the given number N is two digits number, let's say AB and we are counting digit K (1..9).

IF B is less than K THEN 0 ELSE 1
IF A is less than K THEN A ELSE A + 10

Your example Input: K=2, N=35

5 is greater than 2 -> count = 1 (this is digit 2 in number 32)
3 is greater than 2 -> count += 3 (this are twos in 2, 12, 22) + 10 (this are 20,21,22,23,24,25,26,27,28,29)
*22 is counted twice

so we count 1 + 3 + 10 = 14 twos

C# Code example (n = 1..99, k = 1..9):

int numberOfKsBetween0AndN (int n, int k)        
{
    int power = 1;
    int counter = 0;

    while (n > 0)
    {
        int d = n % 10;
        n /= 10;

        counter += (d < k ? 0 : power) + d * power / 10;
        power *= 10;
    }

   return counter;
}

Improved code for n > 100

UPDATE

There was an error in condition I didn't take in account digits when d is equal to k, for k=2, N=2145 my algorithm didn't take in account fist digit two in 2000..2145. Now it works as it should (pass all tests):

    int numberOfKsBetween0AndN (int n, int k)   
    { 
        int originalNumber = n;
        int power = 1;
        int i = 0;
        int counter = 0;            

        while (n > 0)
        {
            int d = n % 10;
            n /= 10;

            counter += d * (power * i) / 10;

            if (d > k)
                counter += power;
            else if (d == k)
                counter += originalNumber % power + 1;

            power *= 10;
            i++;
        }

        return counter;
    }

UPDATE 2

For k=0 (including 0 and n) is easier, you just need to count numbers divisible by 10, 100, 1000, etc.

int numberOf0sBetween0AndN(int n)
{
    int power = 1;            
    int counter = 1;

    while(power < n)
    {                
        power *= 10;
        counter += n / power;
    }

    return counter;
}