获取范围内至少出现1次7的数字数量

Question

我想知道Python中有多少数字至少包含一个7。例如：

• 7有效
• 123无效
• 765有效
• 777有效

这是我正在使用的：

print(len([x for x in range(int(input())+1) if "7" in str(x)]))

它很有效，但对于大量数据来说速度非常慢。有没有更快的方法可以用数学算法计算(注意我用了"计算"而不是"查找"(有多少数字符合条件？

几件事：

• 不接受Brute force算法(例如以任何方式迭代所有内容(
• 不需要额外的模块(例如，从pip安装模块(
• 通过"；"更快"；，我的意思是从输入到输出的时间应该小于1秒(1000ms(
• 如果你的解决方案有点复杂，我想要一个解释，这样我就可以学到一些东西(例如来源/参考文献(

请帮我解决这个问题，谢谢！

Answer 1

我找到了这个解决方案：

def count(n: int) -> int: # function to find numbers with 7
if n < 7: return 0
d: int = len(str(n)) - 1
p: int = 10 ** d
m: int = n // p # most significant digit
t: int = p - 9 ** d # for example, count of 10^2 is 10^2-9^2
if m == 7:  return m * t + n % p + 1 # if n = 778, return the count of 0-699 + 701-778 + 700
elif m > 7:  return (m - 1) * t + p + count(n % p) # if n = 987, return (0-699 + 800-899) + 700-799 + 900-987
else: return m * t + count(n % p) # if n = 123, return 0-99 + 100-123 (found by recursion)
# return (m - (1 if m > 7 else 0)) * (10 ** d - 9 ** d) + (n % p + 1 if m == 7 else count(n % p) + (p if m > 7 else 0))
# def count(n: int) -> int: return 0 if n < 7 else (n // (10 ** (len(str(n)) - 1)) - (1 if n // (10 ** (len(str(n)) - 1)) > 7 else 0)) * (10 ** (len(str(n)) - 1) - 9 ** (len(str(n)) - 1)) + (n % (10 ** (len(str(n)) - 1)) + 1 if n // (10 ** (len(str(n)) - 1)) == 7 else count(n % (10 ** (len(str(n)) - 1))) + (10 ** (len(str(n)) - 1) if n // (10 ** (len(str(n)) - 1)) > 7 else 0))
print(count(int(input())))

随意忽略评论的台词(我无聊时只做了一句台词(。

该解决方案比暴力解决方案快得多。

Answer 2

如果我没有弄错的话，蛮力算法的时间复杂度是o(n(。我找到了一种使它成为o(log10(n((的方法，我希望它足够快。由于以下观察结果，该算法有效：

设f(x(是我们想要的函数。

f(20(=2f(10(

f(30(=3f(10(

但f(100(=9f(10(+10

因为70到80之间的每一个数字都需要计数。我们可以推断出两个重要的性质：

1. f(x10^y(=xf(10^y=sup>(

如果x<7和

2. f(10^x(=9f(10x-1

这可以为我们的案例解决：

• f(x(=x-9^ln(x(/ln(10(

但是，这个函数只适用于10的幂，所以我们将其称为g(x(。这大大简化了问题。现在我们不需要检查x之前的每个数字，只需要检查它前面的10的幂。我找到了一种方法来在python中实现这个想法，但它相当混乱。如果你能改进它或找到更好的配方，请告诉我。

from math import log as ln
# I know that you said 'no modules' but I need logarithms :)
def g(x):
return x - 9**(ln(x)/ln(10))
def step(x): # step function
if x < 7:
return 0
else:
return 1
def int_(x): # same as int() but returns 0 for ''
if x == '':
return 0
else:
return int(x)

def get_7s(num):
answer = 0

str_num = str(num)

if '7' in str_num:
split = str_num.split('7', 1) # cut the number at the first '7' occurence
answer += int_(split[1]) + 1 # add the second half to the answer
str_num = str(int(split[0] + '7' + (len(split[1]))*'0') - 1)
# comes back to the integer before 
# 1379 -> 1369
# 18753 -> 18699
else:
pass

for power_of_10, digit in enumerate(str_num[::-1]): # [::-1] lets us go power of 10 by power of 10
digit = int(digit)
answer += (digit - step(digit)) * g(10**power_of_10) + step(digit) * 10**power_of_10
# the idea is to make property 1 work for all x.
# Two modifications are necessary:
# 'digit - step(digit)' to avoid counting 7s twice. 
# '+ step(digit) * 10**power_of_10' because if step(digit) returns 1,
# it means that a 7 was passed in the counting, so we need to add them back
return answer

测试：

print(len([x for x in range(8756+1) if "7" in str(x)]))
>> 3087
print(get_7s(8756))
>> 3087

而且它比原来的快得多：

%timeit len([x for x in range(10_000_000) if "7" in str(x)])
>> 1.91 s ± 51 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit get_7s(10_000_000)
>> 9.73 µs ± 406 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

我希望这能有所帮助！