Question: Given a positive integer (nature number) N, count the number of ‘1’s between number 1 to N inclusive.
For example, when N = 2, the answer is 1, because only number 1 has a single 1. when N = 13, the numbers, 1, 2, 3, … 10, 11, 12, 13 has total 6 ‘1’s.
Naive Solution
The bruteforce is the simplest solution and it works great for small input N. The idea is to loop (iterative) numbers directly from 1 to N and count the one’s for each individual numbers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | long CountOne1(long n) { long i = 0, j = 1; long count = 0; for (i = 1; i <= n; i ++) { j = i; while (j != 0) { if (j % 10 == 1) count ++; j /= 10; // check rest digits } } return count; } |
long CountOne1(long n)
{
long i = 0, j = 1;
long count = 0;
for (i = 1; i <= n; i ++)
{
j = i;
while (j != 0)
{
if (j % 10 == 1)
count ++;
j /= 10; // check rest digits
}
}
return count;
}The naive approach is easy to understand but its complexity is O(N * LogN) which is inefficient for large input N.
Recursion (Divide and Conquer)
We can solve this problem by decompose the problem into smaller ones. For example, if it is a single digit-number (less than 10) then we know the answer is one. Otherwise, we can always split this number into two parts. The highest digit (left-most) and the remainder. If we use f(n) to denote the answer, then f(12) = f(10 – 1) + f(12 – 10) + 3 where 3 is the numbers that have the highest digit 1, which is 10, 11, 12. f(132) = f(100 – 1) + f(132 – 100) + 33 where 33 are the numbers that have the highest digit 1, which are 100 to 132. Another example, f(232) = 2 * f(100 – 1) + f(32) + 100. 232 is larger than 199, therefore, it contains all the numbers that have the highest digit equal to 1, which are 100 to 199, total 100.
Based on this, we can conclude a recursive formula for f(n), which is
if h = 1: f(n) = f(10^b - 1) + f(n - 10^b) + n - 10^b + 1 else: f(n) = h * f(10^b - 1) + f(n - h * 10^b) + 10^b
where the h is the highest digit (left-most) of number n and b is the number of digits of n minus one.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | long CountOne2(long n) { if (n == 0) return 0; if (n < 10) return 1; long count = 0; long highest = n; int weight = 1; while (highest >= 10) { highest /= 10; weight *= 10; } if (highest == 1) { count = CountOne2(weight - 1) + CountOne2(n - weight) + n - weight + 1; } else { count = highest * CountOne2(weight - 1) + CountOne2(n - highest * weight) + weight; } return count; } |
long CountOne2(long n)
{
if (n == 0)
return 0;
if (n < 10)
return 1;
long count = 0;
long highest = n;
int weight = 1;
while (highest >= 10)
{
highest /= 10;
weight *= 10;
}
if (highest == 1)
{
count = CountOne2(weight - 1)
+ CountOne2(n - weight)
+ n - weight + 1;
}
else
{
count = highest * CountOne2(weight - 1)
+ CountOne2(n - highest * weight)
+ weight;
}
return count;
}The advantage of this approach is that we don’t actually need to iterative numbers from 1 to N in order to compute f(N).
The algorithmic complexity seems O(log(N)) (maybe I am wrong). It is a lot faster than the naive approach but it suffers the inherent recursive problem (the compiler will not know how to optimise this, e.g. make it tail recursive [recommend to read]): when input number is large, the stack will overflow and/or gives incorrect results.
Iterative Counting
Let’s do it differently. We can count the number of 1’s for each different positions, ONEs, TENs, HUNDREDs etc and sum them up.
For number less than 10, the answer is 1. For two-digit numbers, e.g. when N=13, there are 2 numbers that the position (ONEs) has 1, which is 1 and 11. There are 4 numbers that the highest digit (TENs) is 1, which is 10, 11, 12 and 13. Therefore f(13) = 2 + 4.
Another example, when N = 23, there are 3 numbers for position ONE, which are 1, 11 and 21. There fore 10 numbers for position TEN, which are from 10 to 19. therefore, f(23) = 3 + 10
When N=123, the numbers for ONEs are 1, 11, 21, … 91, 101, 111 and 121. The numbers for TENs are 10~19, and 110~119. The numbers for HUNDREDs are 100~123.
We can continue the analysis and in general, we can cook up this,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | long CountOne3(long n) { long count = 0; long i = 1; long current = 0, after = 0, before = 0; while((n / i) != 0) { current = (n / i) % 10; before = n / (i * 10); after = n - (n / i) * i; if (current > 1) count = count + (before + 1) * i; else if (current == 0) count = count + before * i; else if(current == 1) count = count + before * i + after + 1; i *= 10; } return count; } |
long CountOne3(long n)
{
long count = 0;
long i = 1;
long current = 0, after = 0, before = 0;
while((n / i) != 0)
{
current = (n / i) % 10;
before = n / (i * 10);
after = n - (n / i) * i;
if (current > 1)
count = count + (before + 1) * i;
else if (current == 0)
count = count + before * i;
else if(current == 1)
count = count + before * i + after + 1;
i *= 10;
}
return count;
}The above is a iterative approach and that has a complexity O(logN). It runs as fast as the second approach and it does not have the stack overflow problem. The first naive solution is 400 times slower than the second and third approach.
Another Recursion
Here is another recursion method (Author: Paolo Manco) that runs as fast as the second one (probably the complexity is O(logN)).
1 2 3 4 5 6 7 | long f(int n) // counts how many 1's for number n { long out = 0; for ( ; n != 0; n /= 10) out += (n % 10 == 1); return out; } |
long f(int n) // counts how many 1's for number n
{
long out = 0;
for ( ; n != 0; n /= 10)
out += (n % 10 == 1);
return out;
}The function f counts how many 1’s for number n and the recursive formula is somewhat different:
1 2 3 4 5 6 7 8 9 | long CountOne4(long n) { if (n < 1) return 0; const long d = n / 10; const long u = n % 10; if (u == 9) return CountOne4(d) * 10 + d + 1; return CountOne4(n - (u + 1)) + f(d) * (u + 1) + (u > 0); } |
long CountOne4(long n)
{
if (n < 1) return 0;
const long d = n / 10;
const long u = n % 10;
if (u == 9)
return CountOne4(d) * 10 + d + 1;
return CountOne4(n - (u + 1)) + f(d) * (u + 1) + (u > 0);
}And the author is very kind to give the explanation to his code.
count(1...n) =
count(1...n-(k)) + count(n-(k)+1...n) =
k = (u+1)
count(1...n-(u+1)) + count(n-(u+1)+1...n) =
n = (d*10+u)
count(1...n-(u+1)) + count((d*10+u)-(u+1)+1...n) =
count(1...n-(u+1)) + count((d*10)...n) =
count(1...n-(u+1)) + count((d*10)...(d*10+u)) =
n-(u+1) = (d*10+u)-(u+1) = (d*10-1) = ((d-1)*10+9)
count(1...n-(u+1)) + count((d*10)+0...(d*10)+u) =
count(1...n-(u+1)) + f(d*10)*(u+1)+(u>0) =
count(1...n-(u+1)) + f(d)*(u+1)+(u>0) =
lets define an auxiliar function f(n)=(number of '1' digits in n representation).
lets define the function count(n) = f(1)+f(2)+...f(n) = f(0)+f(1)+f(2)+...f(n)
knowing we can write n as d*10+u (where d and u are both positive integers and u < 10).
Given n and knowing (u == 9), can we know what is the 'u' contributes sum? let's see:
n== 9 => d== 0,u==9 => u_contributes_sum== 1
n== 19 => d== 1,u==9 => u_contributes_sum== 2
n== 29 => d== 2,u==9 => u_contributes_sum== 3
n==239 => d==23,u==9 => u_contributes_sum==24
so... u_contributes_sum = (d+1)
Now we know the u_contributes_sum value we can say:
count(n) =
count(d*10+9) =
f(0*10+0)+f(0*10+1)+...f(d*10+9) =
u_contributes_sum + 10*f(0*10+0)+10*f(1*10+0)+...+10*f(d*10+0) =
u_contributes_sum + 10*(f(0*10)+f(1*10)+...+f(d*10)) =
u_contributes_sum + 10*(f(0)+f(1)+...+f(d)) =
(d+1) + 10*count(d) < ------- count(n) when u==9
We can write n as d*10+u (where d and u are both positive integers and u < 10).
Let's define an auxiliar function f(n)=(number of '1' digits in n representation).
Let's define the function count(n) = f(1)+f(2)+...f(n) = f(0)+f(1)+f(2)+...f(n)
We have:
f(n) = f(d*10+u) = f(d*10)+f(u) = f(d)+f(u)
Case (u == 9):
for every positive integer x:
g(x) = f(x*10+0)+f(x*10+1)+...+f(x*10+9) =
{f(x)+f(0)}+{f(x)+f(1)}+...+{f(x)+f(9)} =
f(x)*10+{f(0)+f(1)+...+f(9)} =
f(x)*10+count(9) =
f(x)*10+1
count(n) = g(0)+g(1)+...+g(d) =
{f(0)*10+1}+{f(1)*10+1}+...+{f(d)*10+1} =
{f(0)+f(1)+...+f(d)}*10+(d+1) =
count(d)*10+(d+1)
-----------------------------------------------------
Case (u < 9):
count(n) = count(n-k)+{f(n-k+1)+...+f(n)}
Let's choose k = (u+1):
count(n) = count(n-(u+1)) + {f(n-(u+1)+1)+...+f(n)} =
count(n-(u+1)) + {f(n-u)+...+f(n)} =
(A) (B)
the A term is computed using the case (u==9):
A = count(n-(u+1)) =
count(d*10+u-(u+1)) =
count(d*10-1) =
count((d-1)*10+9)
B = f(n-u)+...+f(n) =
{f(d*10+u-u)+...+f(d*10+u)} =
{f(d*10)+...+f(d*10+u)} =
{f(d*10+0)+...+f(d*10+u)} =
{f(d)+f(0)}+...{f(d)+f(u)} =
f(d)*(u+1)+{f(0)+...f(u)} =
f(d)*(u+1)+count(u) =
f(d)*(u+1)+(u>0)
So, we have:
count(n) = count(n-(u+1)) + f(d)*(u+1)+(u>0)
–EOF (Coding For Speed) —
loading...
Next Post: C++ Coding Example, Using Hash Algorithm to Remove Duplicate Number by O(n)
The problem can be approached using string operations.
Below is a more generic solution.
a = int(input(“Please input the value of a: “))
b= int(input(“Please input the value of b: “))
n = int(input(“Please input the value of n: “))
def counting_machine(a,b,n):
c=[]
for i in range(a, b+1):
d = [d for d in str(i)]
c = c+d
print(c)
b=str(n)
count=0
for i, number in enumerate(c):
if c[i] == b:
count+=1
print(count)
counting_machine(a,b,n)