LintCode算法刷题之尾部的零

链接:尾部的零

描述

设计一个算法，计算出n阶乘中尾部零的个数

样例

样例 1:
输入: 11
输出: 2
样例解释:
11! = 39916800, 结尾的0有2个。

样例 2:
输入: 5
输出: 1
样例解释:
5! = 120， 结尾的0有1个。

挑战

O(logN)的时间复杂度

算法思路

  首先,我们需要知道N的阶乘是如何运算的

  N! 代表N的阶乘
  N! = 1 * 2 * 3 * 4 * 5 * 6 * 7 ... * N-1 * N
 
  简而言之,就是从1乘到N
 
  然后,我们需要知道尾部的0是如何出现的
 
  经过观察,我们发现尾部的0是 5和偶数相乘 得到的
 
  所以该问题转换为从1乘到N,里面有多少个5相乘
 
 
  从1开始,那么每数5个数一定是5的倍数,即最少含有一个5进行最后的乘法运算
 
  所以我们首先以5作为步长,可查出有多少个符合条件的数 即 a = N/5
 
  我们定义sum = 0 为N的阶乘尾部的0的结果
 
  我们将算得的数字加起来 sum += a
 
  它们类似:
      5 10 15 20 25 30 35 40 45 50 55 60...
 
  但其中有些5的倍数中,还存在多个5相乘,比如25是5 * 5,125是5 * 5 * 5,也需要计算出来
 
  根据规律,每5个又会多出现一个5,所以再除以5  a = a/5
 
  我们将算得的数字加起来 sum += a
 
  它们类似:
     25 50 75 100 125 150 175 200 225 ...
 
  此时我们已经计算出两个5,但数据中还可能出现包含更多5的数字,如125包含3个5相乘,也需要计算出来
 
  根据规律,每5个又会多出现一个5相乘,所以再除以5  a = a/5
 
  我们将算得的数字加起来 sum += a
 
  以此类推,直至除得的结果除不开五,sum即为所求0的数量

代码

    public static long getZero(long num) {
        long sum = 0;
        while (num != 0) {
            num /= 5;
            sum += num;
        }
        return sum;
    }