algorithm - "2"在0到n的所有数字中出现了多少次

Question

find how many times "2" occurs in all numbers from 0 to n .

示例:n= 112 answer = 22

numbers : 2 , 12 , 20-29 , 32 ...  92 , 102 ,  112  

我想出了以下方法:

设k=n的位数

f(k) = 从 0 到 10^k-1 ..

f(1) = 1 // 2
f(2) = 10*f(1)+ 10^(2-1) // 12 , 20 - 29 , 32 ... 92
f(3) = 10*f(2)+ 10^(3-1)
and so on ...

twos(int n , int k)
{
    if(n<2)
        return 0;
    else if(n<10)
        return 1;

    msb = n/10^k
    remainder = n%10^k

    if(msb==2) // eg 230 ,  calculate 200 ... to 230  , and find twos from 0 on 199  and recursion on 30
        return msb*(f(k)) + (remainder+1) + twos(remainder) // 2*(below 100) + 31 + tows(30)
    else if (msb>=3)
         return msb*(f(k)) + (10^k) + twos(remainder)  // for 312 -> 3*(below 100) + 100 + twos(12)
    else
        return  msb*(f(k)) + twos(remainder)

}  

我的做法是否正确？
如果是这样，有没有比这更快的解决方案？

编辑:
对于这些测试用例，我的方法似乎是正确的，here是模拟
结果:
第一列:n，第二列:蛮力，第三列:我的方法

2 1 1
5 1 1
91 19 19
868 277 277
7783 3359 3359
55576 32718 32718
293911 242093 242093
10179297 7091858 7091858
59939789 51975959 51975959

Answer 1

假设数字由数字组成 n=... n4 n3 n2 n1 .我们要查看所有数字 x<=n并计算数字 2在他们之中。 x应表示为 x=... x4 x3 x2 x1 .首先，我们计算有多少数字的最后一位是 2，x1==2 :

f1(n) = (n+8) / 10

假设除法截断。一些例子:

f1(1) = 0
f1(2) = 1
f1(12) = 2
f1(21) = 2
f1(22) = 3 

现在让我们计算倒数第二个数字为 2 的数字，x2==2 .这类似于 n 的最后一位数字的切割然后计算最后一位数字为 2 的数字:

f2(n) = 10 * f1(n/10)  # almost right

让我们测试一下:

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

我们需要对 n 倒数第二位的情况进行特殊处理。本身就是一个二，n2==2 :

f2(n) = 10*f1(n/10) - 9 + n1 # if n2==2

与 n1 == n % 10 (余数函数)这可以写成:

f2(n) = 10*f1(n/10) - 9 + n%10 # if n2==2

与计算 x3==2 中的数字类似:

f3(n) = 100*f1(n/100) # if n3 != 2
f3(n) = 100*f1(n/100) - 99 + n%100 # if n3 == 2

总结一下我们得到 2 的总数:

f(n) = f1(n) + f2(n) + f3(n) + ...

在 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;
}