阶乘的尾随零

Question

我正在尝试解决这个编码问题：给定一个整数 n，return n!

中尾随零的数量

下面是我的代码（使用 wiki link 编解码器）

    public int trailingZeroes(int n) {
        int count = 0, i = 5;
        while(i<=n){
            count+= n/i;
            i*=5;
        }
        return count;
   }

这适用于所有测试用例，除非 n = Integer.MAX_VALUE 我得到一个 TLE。我如何修复此代码以使其涵盖该测试用例。我在网上看了五篇文章，似乎都同意我的做法。

非常感谢。

所以，我遵循了 long/BigInteger 方法（谢谢大家）：

    public int trailingZeroes(int n) {
    long count = 0;
    for(long i= 5; n/i >= 1; i= i*5){
        count+= n/i;
    }
    return (int)count;
}

Answer 1

您不能编写循环计数器为 int 且上限为 <= Integer.MAX_VALUE 的 for 或 while 循环。

简单递增 (counter++) 会发生什么，循环计数器设置为该值，主体执行，然后计数器递增，导致负数 , Integer.MIN_VALUE。然后一切从头再来。

当循环计数器的数量递增 > 1 或（如此处）相乘时，可能会发生其他奇怪的事情：int 循环计数器无法保存值 > Integer.MAX_VALUE

考虑另一种遍历这些数字的方法。或者单独处理MAX_VALUE。

Answer 2

正如 Iaune 观察到的，当 n 为 Integer.MAX_VALUE 时，您的循环将永远不会终止，因为没有 int 大于该数字（根据定义）。您应该能够重组循环以避免该问题。例如，这是相同的基本方法，但颠倒了：

public int trailingZeroes(int n) {
    int count = 0;

    while (n > 0) {
        n /= 5;
        count += n;
    }

    return count;
}

Answer 3

你的问题是，一旦 i 变得足够大（超过 Integer.MAX_INT / 5），那么行 i*=5; 会导致 i 溢出到 "wrong"价值。有问题的值是 5 的 14 次方，即 6103515625，但溢出到 1808548329.

这样做的结果是循环一直在执行。 i 永远不会成为 <= Integer.MAX_INT 之外的值，因为根本没有 int.

为避免这种情况，您需要 i 是比 int 更大的数据类型。如果您将原始代码中的 i 和 count 更改为 long，则可以正常工作。当然，BigInteger 也可以。

Answer 4

public static void main(String[] args) {
    int result = findFactorialTrailingZero(100);

    System.out.println("no of trailing zeros are " + result);


}

public static int findFactorialTrailingZero(int no) {
    int zeros = no / 5;

    int zeroIncrementNo = 25;
    int zerosIncrementFactor = 1;
    int nextZeroIncrenent = 5;

    for (int i = 1;no >= zeroIncrementNo; i++) {
        zeros=zeros+zerosIncrementFactor;
        zeroIncrementNo=25*(i+1);

        if(i+1==nextZeroIncrenent){
            zerosIncrementFactor++;
            nextZeroIncrenent=nextZeroIncrenent*5;
        }

    }
    return zeros;

Answer 5

public class FactorialNumberTrailingZeros {

    public static void main(String[] args) {
        System.out.println(trailingZeroes(1000020));
    }

    private static int trailingZeroes(int n) {
        int count = 0;
        while (n > 0 && (n % 10 == 0)) {
            n /= 10;
            count ++;
        }
        return count;
    }
}

Answer 6

   /*
    [n/5]+[n/25]+[n/125]+....
    if n<25 then [n/5]
    if n<125 then [n/5]+[n/25]
    if n<625 then [n/5]+[n/25]+[n/125]
    */

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int countTrailingZeroes(int n)
{
    int res=0;                             
    for(int i=5;i<=n;i=i*5){
         res=res+n/i;
    }
    return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin>>n;
cout<<countTrailingZeroes(n);

return 0;
}

输出

25
6

说明： 25!=1.551121e+25 即包含 6 个尾随零

Answer 7

这是我的 python 代码，可以解决您的问题：

    def check(n):
        j,ans=5,0
        while j<=n:
            ans=ans+n//j
            j=j*5
        return ans

阶乘的尾随零

Trailing Zeroes of a Factorial

java

performance

integer