如何统计L和H之间包含的幸运数字的个数？

Question

我已经完成了一项编码游戏评估，但我无法通过关于幸运数字的一项挑战的所有测试。我需要协助。

定义：幸运数字是一个数字中包含6s 或8s 但不能同时包含两者的数字。例如16, 38,666是幸运数字。234，687不是。

任务L：打印和之间的幸运数字数H。

约束：

• L < H

• 记忆：512MB

• 时间：6 seconds

这是我所做的（我选择 Python 作为编程语言）

def is_lucky(nbr):

    nbr = [*str(nbr)]

    if '6' in nbr and '8' in nbr:

        return False

    if '6' in nbr or '8' in nbr:

        return True

    return False

n_lucky_number = 0

for number in range(L, H + 1):

    n_lucky_number += is_lucky(number)

print(n_lucky_number)

L由于超时，我在和H很大（或两者之间的差距）的测试中失败了。

L, H = 1, 1000000000000000000

L, H = 92871036442, 3363728910382456

有人可以帮我优化我的代码吗？

Answer 1

这是一个有趣的问题，@sulav shrestha 已经提供了一个有效的算法。不幸的是，他的回答缺乏一些解释，代码本身可以更清晰。正如其他人指出的那样，您必须想出一个公式才能执行大数字。@user3386109 正确地指出lucky(L,H) = lucky(0,H) - lucky(0,L-1). 从那里让我们看看在 0 和任何给定数字之间有多少幸运数字。在十进制中，任何数字都可以写成十的幂之和：12345 = 1e4 + 2e3 + 3e2 + 4e1 + 5e0那么让我们计算 0 到 之间的幸运数字的数量10^n。它归结为计算 n 位数字的可能组合：没有8，至少有一个6没有6，至少有一个8没有的组合数8是9^n（您可以为 n 位数字中的每一个选择 9 种可能性）。然后删除所有不包含任何6:的组合8^n。所以 0 到 之间的幸运数字的个数10^n是2*(9^n-8^n)。从那里你可以从左到右遍历你的数字并计数：import timedef magic_numbers_until(num):    num_str=str(num)    str_len=len(num_str)    c=[]    count=0    for i,digit in enumerate(num_str):          # we're going from left to right in num        power_ten=str_len-i-1        for k in range(int(digit)):             # summing all magic numbers for this power of ten            if (k==6 or k==8                    # if 6 (resp. 8) was already seen,                or "6" in c or "8" in c):       # you just calculate the combinations without 8 (resp. 6)                count=count+9**power_ten             else:                               # the case described in my answer                count=count+2*(9**power_ten-8**power_ten)                c.append(digit)                if "6" in c and "8" in c:               # if 6 and 8 are in num, all remaining combinations will be non-magic            break    return(int(count))    L=1H=1000000000000000000t0 = time.time()  print(magic_numbers_until(H+1)-magic_numbers_until(L))print(time.time()-t0)

Answer 2

def coo(a):    b=str(a)    l=len(b)    c=[]    count=0    for i,j in enumerate(b):        d=l-i-1        for k in range(int(j)):            if k==6 or k==8:                if k==6 and "8" not in c:                    count=count+9**d                elif k==8 and "6" not in c:                    count=count+9**d                elif "6" not in c and "8" not in c:                count=count+2*((9**d)-(8**d))            elif "6" in c or "8" in c:                count=count+9**d                 c.append(j)                if "6" in c and "8" in c:            break    return(int(count))L=21345323634H=8392440035734    print(coo(H+1)-coo(L))

Answer 3

6秒？这在 Python 中似乎真的很难，与 C、Java 等相比通常很慢。尽管我还没有找到通过测试的方法，但有几个地方可以改进：1. is_luckynbr可以直接转换成str，不需要解压成list. str支持in。使用在数学计算中的事实，True==1，False==0。例如 A is '6' in nbr, B is '8' in nbr:两者都为真，A+B=2一个为真，A+B=1两者都为假，A+B=0所以我们可以检查是否A+B == 1。前：def is_lucky(nbr):&nbsp; &nbsp; nbr = [*str(nbr)]&nbsp; &nbsp; if '6' in nbr and '8' in nbr:&nbsp; &nbsp; &nbsp; &nbsp; return False&nbsp; &nbsp; if '6' in nbr or '8' in nbr:&nbsp; &nbsp; &nbsp; &nbsp; return True&nbsp; &nbsp; return False后：def is_lucky(nbr):&nbsp; &nbsp; nbr = str(nbr)&nbsp; &nbsp; return ('6' in nbr) + ('8' in nbr) == 12.循环如果现在已经检查了数字False，我们可以改进它。如果最后一位小于 5，递增 6-n%10。例如，311不是幸运数字。所以当然 312~315 也不是，所以只需通过6-1=5直接添加到316。 为什么不<6？5 加 1 无论如何，所以我们不需要它:]前：n_lucky_number = 0for number in range(L, H + 1):&nbsp; &nbsp; n_lucky_number += is_lucky(number)print(n_lucky_number)后：number, s = L, 0while n <= H:&nbsp; &nbsp; x = is_lucky(number)&nbsp; &nbsp; n_lucky_number += x&nbsp; &nbsp; m = number % 10&nbsp; &nbsp; if not x and m < 5:&nbsp; &nbsp; &nbsp; &nbsp; number += 6-m&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; number += 1print(n_lucky_number)