Factorial Trailing Zeroes

描述

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

Note: Your solution should be in logarithmic time complexity.

分析

对任意一个正整数n进行质因数分解，n=2x∗3y∗5z...n = 2^x3^y5^z… ，末尾0的个数M与2和5的个数即X、Z有关，每一对2和5都可以得到10，故M=min(X,Z)。又因为能被2整除的数出现的频率要比能被5整除的数出现的频率高，所以M=Z。所以只要计算出Z，就可以得到n!的末尾0的个数。

解法1

  1. // Factorial Trailing Zeroes
  2. // TLE
  3. // Time Complexity: O(nlogn), Space Complexity: O(1)
  4. public class Solution {
  5.     public int trailingZeroes(int n) {
  6.         int result = 0;
  8.         for (int i = 1; i <= n; ++i) {
  9.             int j = i;
  10.             while (j % 5 == 0) {
  11.                 ++result;
  12.                 j /= 5;
  13.             }
  14.         }
  15.         return result;
  16.     }
  17. }

解法2

上面的解法会超时，可以优化一下。

可以用公式计算出末尾0的个数，Z=N/5+N/52+N/53+...Z=N/5 + N/5^2 + N/5^3 + … ，N/5N/5 表示从1到N中能被5整除的数的个数，由于每个数都能贡献一个5，意味着能贡献一个0。N/52N/5^2 表示从1到N中能被 525^2 整除的数的个数，每个数都能贡献2个5，意味着能贡献两个0，不过由于其中一次已经包含在 N/5N/5 中了，只能再贡献一个0，依次类推。

  1. // Factorial Trailing Zeroes
  2. // Time Complexity: O(logn), Space Complexity: O(1)
  3. public class Solution {
  4.     public int trailingZeroes(int n) {
  5.         int result = 0;
  7.         while (n > 0) {
  8.             result += n / 5;
  9.             n /= 5;
  10.         }
  11.         return result;
  12.     }
  13. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/number-theory/factorial-trailing-zeroes.html