Count the number of Ks between 0 and N
Solution 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 of0(...)
, 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 form0***
. - 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.
Solution 2
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;
}
Solution 3
It's simple. Any number can be represented in a special record:
73826 = 9999 + 6*(9999 + 1) + (3826 + 1)
You will need to count the number of these figures for the numbers 9, 99, 999, 9999 ... Then you can put them in the array. Special case - by 0, it uses an array [1, 11, 111, 1111, ...]
Keep in mind that the first digit so also may contain the required value.
Solution 4
For case 0, we need to handle separately,
For general case from 1 to 9:
Assume that we know the number contains k that has x digits and called it m, to calculate all number contains k and has (x + 1) digits, the formula will be :
9*m + (all_number_has_x_digit - m)
The reason is simple, to all number that already contains k, we can insert 1 to 9 as first digit,so we have 9*m. For all number that doesn't contains k, we can add k in front of them, which created all_number_has_x_digit - m).
To calculate the number of k appears from all these numbers, the formula should be similar, (By maintaining both values : the amount of numbers that contain k and the number of appearances of k) this is just an idea for you to start :)
Related videos on Youtube
herohuyongtao
Stack Exchange Data Explorer - You're an amateur developer until you realize that everything you write sucks. - We're going to go that way, really fast. And if something gets in our way, we'll turn.
Updated on October 08, 2022Comments
-
herohuyongtao over 1 year
Problem:
I have seen questions like:
count the number of 0s between 0 and N?
count the number of 1s between 0 and N?
count the number of 2s between 0 and N?
- ... ...
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
2
s between[0,35]
:2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32
, note that22
will be counted as twice (as22
contains two2
s)
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
2
s part in the above code to1
s in order to solve the problem of counting the number of1
s between0
andN
. It seems that we have to handle differently (not trivial) for different cases.Is there a general procedure we can follow to handle all
K
s (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
-
herohuyongtao over 10 years@Tomas No, it's not. I just want to check if these problems can be solved in a more general way.
-
herohuyongtao over 10 yearsCan you share more details? To me, it seems it's an
O(N log N)
approach. -
Christian Severin over 10 yearsYou can even count every digit in a single pass: build a map for the counters, and use the string's characters as a key. You might as well use an array and calculate the current character's index via something like
c - '0'
. -
herohuyongtao over 10 yearsPlease explain more on how to count the number of different
K's
for e.g. 9999. I am more curious about this. -
herohuyongtao over 10 yearsHow to understand the formula? Will it hold for all
K's
? -
user3164559 over 10 years9999 = 999 + 8*(999 + 1) + 999 + 1 Depending on the numbers that you need.
-
herohuyongtao over 10 yearsYour code will fail in some cases. For example, for
n=100, k=2
, the result should be 20 while your code will give 10. -
Branimir over 10 yearsYes you are right, it works for n = 1..99 and k = 1..9. So for n=99 and k = 2 will return 20 as expected.
-
herohuyongtao over 10 yearsAny idea on how to extend this function to handle large numbers?
-
Branimir over 10 yearsCan you check results now? Updated code should work for arbitrary n.
-
herohuyongtao over 10 yearsThanks for the update. However, it will still fail for e.g. case
n=2000, k=2
, which should be 600 instead of 1600. -
Branimir over 10 yearsCan you define test cases? I will try to make it work. There was error in condition instead of (d < k ? 0 : power), condition should be (d <= k ? 0 : power).
-
herohuyongtao over 10 yearsI tested your updated version. It works for most cases. But still, it will fail for
K=2, N=2145
or simpler caseK=1, N=1
. -
Tim over 10 years@herohuyongtao Updated~
-
herohuyongtao over 10 yearsThanks for your update. For the code for
k≠0
, it works for most cases. However, it will fail whenk=2, n=2000
, result should be600
instead of601
. Please have a check. -
Tim over 10 years@herohuyongtao I might say k=2,n=2000 is 601, because of the checker, what is your result when k=2,n=1999?
-
herohuyongtao over 10 years600 for
k=2, n=1999
. -
Tim over 10 years@herohuyongtao So, that's much clear, 601 is for
k=2,n=2000
,2000
has one2
matched. -
herohuyongtao over 10 yearsGood work by solving it iteratively. Can you also share your code for
k=0
? -
arviman over 7 yearsAny link to the mathematics behind this would be appreciated as I cannot grok it quiet yet. Seems to me like all you're doing is 73286 = 7*10000+3286 except you split the 7*10000 as 6*(9999+1) + 999 + 1 (which you add with 3286)
-
arviman over 7 yearsIt's a slow approach esp. if n is very large. It's basically O(nm) where m is the size of digit.
-
saadi almost 5 years@Branimir nice work. If you have time, can you explain the solution a little bit? Like how are you solving the problem? The though process?
-
Branimir almost 5 years@saadi Thank you. I tried to explain the thought process in the first part of the answer. If you have some specific question I'll try to answer. In general, try to write down an example and solve it manually on paper. After you solve a few examples manually, a pattern may show up, test if it is a general solution. Practice helps too :)