algorithm - 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

I believe this is what's your need, simple, general and fast.

Below is an example in Python:

Slow Checker

The checker is simple, use string to find all number in string from '0' - 'n', and count the match times of k, it's slow but we can use it to check other solutions.

import string       

def knChecker( k, n ):
    ct = 0
    k = str(k)
    for i in xrange(0,n+1):
        ct += string.count(str(i),k)
    return ct   

Fast and General Solution

k ≠ 0

for every k = [1,9],it's much clear that in [0,9] we can find 1 match in first bit;

in [0,99] we can find 1 matches in first bit and 10 matches in second bit, so all is 1*10^1 + 10*10^0 = 20 matches,

in [0,999] we can find 1 matches in first bit ,10 matches in second bit and 100 matches in third bit, so all is 1*10^2 + 10*10^1 + 100*10^0 = 300 matches...

So we can easily conclude that in [0,10^l - 1], there is l * 10^(l-1) matches.

More general, we can find in [0,f * 10^l - 1], there f*10^(l-1) * l matches.

So here is the solution:

for example, n = 'abcd', k = 'k'

• step1: if n = 0 or n = '', return 0; count matches in 'a000', use the up formula, l = len(n)
• step2A: if a == k, we know all 'bcd' is matched, so add bcd matches.
• step2B: if a > k, we know all 'k***' is matched, so add 10^(l-1) matches.
• step3: cut the first bit a, and set n = 'bcd', go to step1

Here is the code for k ≠ 0:

def knSolver( k, n ):
    if k == '0':
        return knSolver0( n, 0 )
    if not n:
        return 0
    ct = 0
    n = int(n)
    k = int(k)
    l = len(str(n))
    f = int(str(n)[:1])
    if l > 1:
        ct += f * 10 ** (l-2) * (l-1)
    if f > k:
        ct += 10 ** (l-1)
    elif f == k:
        ct += n - f * 10 ** (l-1) + 1
    return ct + knSolver( k, str(n)[1:])

k = 0

k = 0 is a bit of tricky, because 0*** is equal to *** and will not allowed to count it marches '0'.

So solution for k ≠ 0 can't fit k = 0. But the idea is similar.

We can find that if n < 100, there must be n/10 + 1 matches.

if n in [100,199], it's much similar that as k ≠ 0 in [0,99], has 20 matches;

if n in [100,999], it's much similar that as k ≠ 0 in [100,999], has 20 * 9 matches;

if n in [1000,9999], it's much similar that as k ≠ 0 in [1000,9999], has 300 * 9 matches...

More general, if n in [10^l,k*10^l-1], it will has l*10^(l-1)*k matches.

So here is the solution:

for example, n = 'abcd', k = '0', recurse step s = 0

• step0: if n = '', return 0; if n < 100, return n/10+1;
• step1A: n='f(...)', f is first bit of n. if s > 0, say we have handled the first bit before, so 0 can treat as k ≠ 0, so if f == 0, all rest (...) should match, just add (...)+1 matches.
• step1B: if s > 0 and f > 0, l = len(n), we know there will be 10 ** (l-1) matched in the first bit of 0(...), and (l-1) * 10 ** (l-2) in (...)
• step2: if s == 0, count matches in 'f(...)-1', use the up formula
• step3: if s > 0, just check for (...) as s == 0 in step2, will get (f-1) * 10 ** (l-2) * (l-1), (f-1), because we can't start form 0***.
• step4: cut the first bit f, and set n = '(...)', s += 1, go to step1

Here is the code of k = 0:

def knSolver0( n, s ):
    if n == '':
        return 0
    ct = 0
    sn = str(n)
    l = len(sn)
    f = int(sn[:1])
    n = int(n)
    if n < 100 and s == 0:
        return n / 10 + 1
    if s > 0 and f > 0:
        ct += 10 ** (l-1) + (l-1) * 10 ** (l-2)
    elif s > 0 and f == 0:
        ct += n + 1
    if n >= 100 and s == 0:
        ct += 10
        for i in xrange(2,l):
            if i == l-1:
                ct += i * 10 ** (i-1) * (f-1)
            else:
                ct += i * 10 ** (i-1) * 9
    elif s > 0 and f != 0:
        ct += (f-1) * 10 ** (l-2) * (l-1)
    return int(ct + knSolver0( sn[1:], s+1 ))

Test

print "begin check..."
for k in xrange(0,10):
    sk = str(k)
    for i in xrange(0,10000):
        #knSolver( sk, i )
        if knChecker( sk, i ) != knSolver( sk, i ):
            print i, knChecker( sk, i ) , knSolver( sk, i )
print "check end!"

Test all k[0,9] from n[0,10000], it passed all cases.

The test will take a bit long time, because of the checker is slow. If remove the checker, all cases in my laptop take about one second.