leetcode：172. 阶乘后的零

题目

给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

示例：

  1. 输入：n = 3
  2. 输出：0
  3. 解释：3! = 6 ，不含尾随 0
  1. 输入：n = 5
  2. 输出：1
  3. 解释：5! = 120 ，有一个尾随 0
  1. 输入：n = 0
  2. 输出：0

解答 & 代码

  1. 原题目：求 n! 结果中尾随零的数量
  • 两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，2 * 5 = 10
  1. 可转换为：求 **n!** 最多可以分解出多少个因子 2 和 5？
  • 每个偶数都可以分解出因子 2，因此因子 2 的数量肯定比因子 5 多

  1. 可转换为：求 **n!** 最多可以分解出多少个因子 5？

    1. 每个 div=5 的倍数都至少可以提供一个因子 5，n! 中有 n/5 个 5 的倍数
    2. 每个 div=25 的倍数还可以再提供一个因子 5，n! 中有 n/25 个 25 的倍数
    3. 每个 div=125 的倍数还可以再提供一个因子 5，n! 中有 n/125 个 125 的倍数
    4. …

    5. 因此，依次遍历 div = 5, 25, 125..., 直到 div > n 停止遍历。对于每个 div，n! 中有 n/div 个 div 的倍数，尾随零的个数就 +n/div

      1. class Solution {
      2. public:
      3. int trailingZeroes(int n) {
      4.   if(n <= 0)
      5.       return 0;
      7.   int result = 0;
      8.   int div = 5;
      9.   while(div <= n)
      10.   {
      11.       result += n / div;
      12.       div *= 5;
      13.   }
      14.   return result;
      15. }
      16. };

      复杂度分析：整数 n

  • 时间复杂度[中等] 172. 阶乘后的零 - 图1：
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：5.7 MB, 在所有 C++ 提交中击败了 87.85% 的用户