其他题目---有关阶乘的两个问题

时间：2021-01-05 06:17:18

【题目】

　　给定一个非负整数N，返回N！结果的末尾为0的数量。
　　例如：3! = 6，结果的末尾没有0，所以返回0。5! = 120，结果的末尾有1个0，返回1。1000000000!，结果的末尾有249999999998个0，返回2499999998。

【进阶题目】

　　给定一个非负整数N，如果用二进制数表达N!的结果，返回最低位的1在哪个位置上，认为最右边的位置为位置0.
　　例如：1! = 1，最低位的1在位置0上。2! = 2，最低位的1在1位置上。1000000000!，最低位的1在999999987位置上。

【题目】

　　无论是原问题还是进阶问题，通过计算出真实的阶乘结果后再处理的方法无疑是不合适的，因为阶乘的结果往往很大，非常容易溢出，而且增加计算的复杂性。

　　原问题。
　　普通解法。对原问题来说，N!的结果的末尾有多少个0可以等价为在序列1,2,3…N中有多少个因子5。这是因为在 1*2*3*…*N的过程中，因子2的数目一定要比因子5的数目多，所以不管有多少个因子5，都有足够的2与其相乘得到10。所以只要找出1～N所有的数中，一共含有多少个因子5就可以。

#python3.5
def zeroNum1(num):
if num <= 0:
return 0
    res = 0
for i in range(5, num+1, 5):
        cur = i
while cur % 5 == 0:
            res += 1
            cur //= 5
return res

　　普通解法对于每一个数i来说，处理的代价是 log5i ，一共有O(N)个数。所以时间复杂度是O( N∗log5N )。

　　原问题最优解。首先我们把1～N的数列出来：1,2,3,4,5,6,7,8,9,10…15…20…25…30…35……75…100…125…

　　我们可以发现每隔5个数(5,10,15,20…)都至少含有一个因子5，将这个数列拿出来(5,10,15,20,25,30,35,40,45,50…)，我们又可以发现，每隔5个数(25,50,75…)都至少含有两个因子5。同理，数列(25,50,75,100…)每隔5个数至少含有三个因子5……

　　总结一下就是：1～N个数有 N/5 个数，这每个数都能贡献一个5；然后1～N中有 N/52 个数，这每个数又能贡献一个5……

　　因此，如果把N!的结果中因子5的总个数记为Z，可以得到如下关系：Z = N/5+N/52+N/53...+N/5i (i一直增长，直到 5i>N )。

　　时间复杂度O( log5N )。

def zeroNum2(num):
if num <= 0:
return 0
    res = 0
while num != 0:
        res += num // 5
        num //= 5
return res

　　进阶问题。
　　解法一。与原问题相似，最低位的1在哪个位置上，完全取决于1～N的数中因子2有多少个，因为只要一出现一个因子2，最低位就会向左移动一位。过程与原问题的最优解法一样。

def rightOne1(num):
if num < 1:
return -1
    res = 0
while num != 0:
        num >>= 1
        res += num
return res

　　解法二。如果把N!的结果中因子2的总个数记为Z，把N的二进制数表达式中1的个数记为m，还存在如下一个关系Z = N - m，也就是可以证明N/2 + N/4 + N/8+… = N-m。（这里的/指的是整除）。
　　
　　首先，如果一个整数K正好是2的某次方，那么 K/2 + K/4 + K/8+… = K/2 + K/4 + K/8+…+1。根据等比数列求和公式 S=a1−anq1−q ，可以得到 K/2 + K/4 + K/8+… = K-1。

　　如果在N的二进制表达中有m个1，那么N可以表达为：N = K1 + K2 + K3 + …+ Km，其中所有的K都等于2的某次方，例如，N = 10110时，N = 10000+100+10(这里的数都是二进制数)。于是有
　　 N/2 + N/4 +… = (K1 + K2 + K3 + …+ Km)/2 + (K1 + K2 + K3 + …+ Km)/4 +… = K1/2 + k1/4 + …+ 1 + K2/2 + k2/4 + …+ 1……

　　K1,K2,K3…Km都是2的某次方。所以等式右边 = K1-1 + K2-1 + K3-1 +…+Km-1 = (K1 + K2 + K3…) - m = N-m。至此，Z = N - m证明完毕。

#python3.5
def rightOne2(num):
if num < 1:
return -1
    res = 0
    tmp = num
while tmp != 0:
if tmp & 1 != 0:
            res += 1
        tmp >>= 1
return num - res
标签：

相关文章