快速查找2的幂数位

Question

任务是搜索2 ^ 10000以下的每个2的幂,返回包含字符串的第一个幂的索引.例如,如果要搜索的给定字符串是"7",则程序将输出15,因为2 ^ 15是其中包含7的第一个幂.

我通过蛮力尝试来解决这个问题,大约70%的测试用例超时.

for i in range(1,9999):
    if search in str(2**i):
        print i
        break

如何以5秒的时间限制接近这个？

Answer 1

尽量不要2^i在每一步计算.

pow = 1
for i in xrange(1,9999):
    if search in str(pow):
        print i
        break
    pow *= 2

您可以随时计算它.这应该可以节省大量的计算时间.

使用xrange将阻止列表的构建,但这可能不会产生太大的影响.

in可能实现为二次字符串搜索算法.它可能(或可能不会,你必须测试)更有效地使用像KMP这样的字符串搜索.