java - 使用 long 而不是 int 时程序更快

Question

我正在尝试解决以下问题:

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

我提交了以下代码，但由于速度太慢而被拒绝:

public int trailingZeroes(int n) {
        int result = 0;
        int k = 5;

        while (k <= n){
            result += n / k;
            k *= 5;
        }

        return result;
    }

但是当我把变量k改成long的时候，已经够快了/

为什么当我声明 k 为 long 而不是 int 时速度更快？ (我读了 this question，如果我理解正确的话，应该会发生相反的情况)

Answer 1

@Tunaki 的评论可能是关于钱的。如果您的 n 大于 Integer.MAX_VALUE/5，则 k 有可能达到大于 Integer.MAX_VALUE 的值/5，然后乘以 5 后溢出，又变成一个小数，所以你的程序永远不会终止。

然而，如果 k 是一个 long，那么它的值是否大于 Integer.MAX_VALUE/5 并不重要；只要它小于 Long.MAX_VALUE/5(这是肯定的，因为 n 是一个 int 而 int 永远不会达到足够接近的值)，溢出就不会不会发生。