Let's say the number consists of digits n=... n4 n3 n2 n1
. We want to look at all numbers x<=n
and count the digits 2
within them. x
shall be represented as x=... x4 x3 x2 x1
. As a start, we count how many numbers have a 2 as last digit, x1==2
:
f1(n) = (n+8) / 10
assuming the division truncates. Some examples:
f1(1) = 0
f1(2) = 1
f1(12) = 2
f1(21) = 2
f1(22) = 3
Now let's count the numbers that have a 2 as second to last digit, x2==2
. This is similar to cutting of the last digit of n
and then counting the numbers that have a two as last digit:
f2(n) = 10 * f1(n/10) # almost right
Let's test it:
f2(10) = 0
f2(20) = 10 * f1(2) = 10 # wrong
f2(25) = 10 * f1(2) = 10 # wrong
f2(29) = 10 * f1(2) = 10
f2(30) = 10 * f1(3) = 10
We need special handling for the case when the second to last digit of n
is a two itself, n2==2
:
f2(n) = 10*f1(n/10) - 9 + n1 # if n2==2
With n1 == n % 10
(remainder function) this can be written as:
f2(n) = 10*f1(n/10) - 9 + n%10 # if n2==2
Similarly for counting the numbers where x3==2
:
f3(n) = 100*f1(n/100) # if n3 != 2
f3(n) = 100*f1(n/100) - 99 + n%100 # if n3 == 2
Summing it all up we get for the total number of 2's:
f(n) = f1(n) + f2(n) + f3(n) + ...
In Java:
public static int count2(int n) {
int res = (n+8) / 10;
int divider = 10;
while (n>= 2*divider){
int na = n / divider;
res = res + divider * ((na+8) /10);
if (na%10==2)
res = res - divider + 1 + n % divider;
divider = divider * 10;
}
return res;
}