Posts pythonTip 11 结尾0的个数
Post
Cancel

pythonTip 11 结尾0的个数

题目描述:

给你一个正整数列表 L, 输出L内所有数字的乘积末尾0的个数。(提示:不要直接相乘,数字很多,相乘得到的结果可能会很大)。

例如: L=[2,8,3,50],

则输出:2

分析

把列表里面所有的数都乘起来,最后再去统计末尾 0 的个数也可以。 但是这样就像题目说的一样,结果可能会很大。

在累计相乘的过程中,顺便数 0 的个数,那么最后的结果依然可能会比较大。

并且虽然 python 的整数没有位数的限制,但是在比较大的整数相乘的时候,性能就会下降,毕竟python底层是C语言实现的,而C语言对于整数是有限制的。

那么我们再分析一下,两个数相乘,可能会出现末尾 0 的情况。

2 * 5 = 10 4 * 5 = 20 4 * 25 = 100 8 * 125 = 1000 2 * 10 = 20

其实,多测试几组数,我们就可以得出一个结论。 如果末尾有 0, 那么就一定是 10 的倍数。 (这是一个傻傻的结论)

而10 = 2 * 5 = 1 * 10 所以两个数相乘为10,就一定有 2 和 5,或者是 2 和 5 的倍数。(PS: 1 和 10 没必要分析了。) 并且每一对,2,5 就可以得到一个 10 也就是 1 个 0. 那么最后问题就变成了数 数组中 每个数的因子中 2, 5 的个数。 并且取最少的一个。那就是最后0 的个数。 例如: 8 = 2 * 2 * 2 125 = 5 * 5 * 5 所以 8 * 125 = 1000 有 3 个 0

res, res_2, res_5 = 0, 0, 0
for num in L:

    while num % 2 == 0:
        res_2 += 1
        num //= 2
    
    while num % 5 == 0:
        res_5 += 1
        num //= 5

res += min(res_2, res_5)
print(res)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 10 最下公倍数

pythonTip 12 结尾非零数的奇偶性

Trending Tags