這是讀書時一篇舊文搬運.幾年後再次回顧下算法.

問題

給定一個數字n，求1到n序列中2出現的總次數。n最大值可能是10^9。

思路

暴力

依次求解1..n每個數含有多少個2，最後求和。

給定數字n，其位數（10進制）為logn，具體的時間復雜度大致如下：

T(n) = log_{10}n + log_{10}{(n-1)} + ... + log_{10}{1} = log_{10}{n!} = O(log_{10}{n!}) Rightarrow T(n) = O(log{n^n}) = O(nlogn)

所以，暴力法時間復雜度是nlogn的

數位枚舉

換一個枚舉思路，正常的枚舉是 i -> i+1 -> i+2 ...這樣,

現采用數位遍歷的方式，假設n是K位數,所有出現的2，出現的位置隻能在這個范圍內：[0,K-1]。（從0開始比較好算）

所以問題可以轉變為：對於每個 din[0,K-1] ,求符合條件為 in[1,n] 且第d位為2的數字的個數和 S_d ，最後累加 sum_{d=1}^KS_d

關鍵點在於對於第d位為2的數字個數如何求解？

很容易我們可以歸納出數字個數與第d位數字與2的大小關系有關：

PS: 以下的d是從0開始取的。

• 給定n，假設第d位數字小於2,舉個例子：

n = 716130, d = 2， 第d位數字為1，該位為2且滿足小於等於n的數字是：

200 - 299， 1200 - 1299， 2200 - 2299， ..., 715200 - 715299，顯然有716 * 100個

規約下，有:

S_d = n / 10^{d+1} * 10^d qquad text{if} digit(d,n) lt2

• 類似地，假設第d位數字大於2，舉個例子：

n = 716130, d = 3， 第d位數字為6，該位為2且滿足小於等於n的數字是：

2000 - 2999，12000-12999，...,712000-712999，顯然有72*1000個，

規約下，有：

S_d = （n / 10^{d+1}+1） * 10^d qquad text{if} digit(d,n) gt2

• 最後一種可能，假設第d位數字等於2，舉個例子：

n = 716230, d = 2，第d位數字為2，該位為2且滿足小於等於n的數字應該就是第d位小於2的情況下的 S_d 再加上餘出來的716200 - 716230這31個數字

規約下，有：

S_d = n / 10^{d+1} * 10^d + (n - (n mod 10^{d}) + 1) qquad text{if} digit(d,n) = 2

最後遍歷n的每一位，求出這些數字在累加即可。

新算法的復雜度隻與位數相關，也就是O(logn)

總結下來，難點在於如何轉變為數位枚舉的思維方式，即把一般直覺上的子問題：給定一個數字，求這個數字含有的2的個數，轉為，求2在這些數字裡的第d位一共出現瞭幾次==>轉為數符合這樣的數的個數問題。 另外對於某個數字含有多個2而言（如202），其實是被枚舉過程計算多次的，從而符合2的總個數要求。