686. 二的幂(Powers of Two)

在二的幂中,第一个拥有前导数字\(“12”\)的是\(2^7=128\),下一个拥有前导数字\(“12”\)的二的幂是\(2^{80}\)。记\(p(L, n)\)为第\(n\)个使得\(2^j\)的十进制表示拥有前导数字\(L\)的数字\(j\),则\(p(12,1)=7\)

我们已知\(p(123,45)\),求\(p(123,678910)\)

分析:这道题的思路比较直接,我们只需要不断计算二的幂,然后看它的前三位是否等于\(123\)就可以了。需要注意的是,二的幂的增长非常快,虽然\(python\)支持任意精度整数,但是数字太大后所耗费的空间会不断降低程序的运行速度。因为我们只关心二的幂的前三位数,所以一个更好的办法是每当二的幂超过一千也就是三位数时,我们就把它除以十,这样就把整数转化成浮点数,同时小数点后的数字我们都不关心了。对于这样一个数字,我们求其整数部分,如果整数部分为\(123\),我们就将其计数器累加一。这样当计数器达到\(678910\)时,我们返回此时对应的指数,即为题目所求。代码如下:

# time cost = 428 ms ± 4.64 ms

from numba import njit

@njit
def nth_start_with(target=123,N=678910):
    n,power,k = 0,2,1
    while n<N:
        power = power * 2
        while power >= 10**3:
            power = power / 10.0
        if int(power) == target:
            n = n + 1
        k = k + 1
    return k