计算阶乘的最后一个非零数字 - 为什么我的代码通过了一些测试但没有通过其他测试？

Question

我正在编写代码来解决以下 codewars 问题：https://www.codewars.com/kata/5f79b90c5acfd3003364a337/train/python

我的想法是取 1 to n 中的所有整数，取每个整数的最后一位（第 0 栏），将它们相乘，然后 return 'last' 结果的非零位：

def last_digit(n):
    factorials = []
    factorials_n = 1
    for i in range(1,n + 1):
        i = str(i)
        i = i[::-1]
        for j in i:
            if j == "0":
                break
            factorials.append(j)
            break              


    # at this point factorials contains the first non-zero integers of each integer in reverse
    for i in factorials:
        factorials_n = factorials_n * int(i)

    factorials_n = str(factorials_n)
    factorials_n = factorials_n[::-1]


    for i in factorials_n:
        if i != "0":
            return int(i)

该代码通过了多项测试，但 387 (returns 6, should be 2) 和 1673 (returns 2 should be 4) 未通过。我试过将打印语句作为调试，但代码看起来不错，也许是逻辑在某些时候失败了——有什么想法吗？

Answer 1

您的代码通过了直到 24 的数字测试用例，当 25 中的非零数字时失败！给出了一个错误的答案，它被传播到它后面的数字。

我们也可以简单地使用模运算符来获取最后一位数字，而不是将其转换为字符串
示例：1234 % 10 等于 4（这是最后一位）

我的解决方案：

def last_digit(n):

    factorial = 1
    
    for i in range(1, n + 1):
    
        # compute the factorial
        prod = factorial * i
        
        # keep dividing the product by 10 until the last digit is a !0 digit
        while prod % 10 == 0:
            prod = prod // 10
            
        # only store the last 3 digits of the computed product.
        # You can keep more digits to get accurate results for
        # when the numbers are higher than 10000
        factorial = prod % 1000
    
    # return the last digit
    return factorial % 10

正如我之前所说，当最后一个 !0 数字来自 24! (6) 乘以 25，它输出 150，在删除 0 后得到 5，但它应该是 4。因此，为了解决这个问题，我们至少保留最后 3 位数字，而不是仅保留最后一位数字.

Example:   6 * 25 =   150 => 5 (last !0 digit)
         936 * 25 = 23400 => 4 (last !0 digit)

PS: !0 = 非零

Answer 2

这里的问题出在逻辑上。由于您放弃了数字以 0 结尾的所有情况，因此我们无法得出正确答案。

考虑 2 x 8 x 30。要获得阶乘的最后一位，将最后一位相乘就足够了，但要找到最后一位非零数字，您必须计算 2 x 8 x 3 相反。

使用 this 解决方案作为参考，您可以执行以下操作：

def last_digit(n):
    # factorials = []
    # factorials_n = 1
    last = 1
    d2 = 0
    for i in range(1,n + 1):
       
        ii = i
        print(ii)
        while(ii%2==0):
            d2 +=1
            ii = ii/2
        
        while(ii%5==0):
            d2 -=1
            ii = ii/5
        print(d2)
        last = (last * ii)%10
        print(last)
    
    for i in range(0,d2):
        last = (last *2)%10

    return int(last)

计算阶乘的最后一个非零数字 - 为什么我的代码通过了一些测试但没有通过其他测试？

calculating the last non-zero digit of a factorial- why does my code pass some tests but fail others?

python

factorial