使用 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

k 可能会溢出，这意味着您可能会得到一个无限循环（即 k <= n 始终为真的情况，因为 k 可以在相乘时环绕到 INT_MIN 5).

例如，考虑 n 是 INT_MAX 的情况：如果 k 是 int，k <= n 必须为真。

不过，如果 k 是 long，则不会发生溢出。

Answer 2

@Tunaki 的评论可能是在钱上。如果你的n大于Integer.MAX_VALUE / 5，那么k有可能达到大于Integer.MAX_VALUE / 5的值，然后乘以5后溢出，变成小数再次，所以你的程序永远不会终止。

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

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

Faster program when using long instead of int

java

algorithm

int

long-integer