P179 阶乘末尾 0 的个数

描述#

这个题目说的是，给你一个整数 n，你要计算 n! 的结果末尾有多少个 0。

注意，题目要求算法的时间复杂度是 O(log(n))。

比如说，给你的 n 等于 4：
n = 4
4! = 1 x 2 x 3 x 4 = 24
4! 等于 24，末尾没有 0，因此返回 0。
再比如说，给你的 n 等于 5：
n = 5
5! = 1 x 2 x 3 x 4 x 5 = 120
5! 等于 120，末尾有 1 个 0，因此返回 1。

代码#

public class AlgoCasts {

  // Time: O(log_5(n)), Space: O(1)
  public int trailingZeroes(int n) {
    int cnt = 0;
    while (n > 0) {
      n /= 5;
      cnt += n;
    }
    return cnt;
  }

}