阶乘末尾有 n 个零的数

---

一个数的阶乘是所有正整数直到该数的乘积。例如，5 的阶乘表示为 5!，等于所有正整数直到 5 的乘积。

5! = 5 x 4 x 3 x 2 x 1 = 120

一个数的阶乘的十进制表示中末尾零的个数称为阶乘中的“尾随零”。例如，5 的阶乘是 120，它有一个尾随零，而 10 的阶乘是 3,628,800，它有两个尾随零。

问题陈述

给定一个整数 n，我们必须确定阶乘具有 n 个尾随零的正整数的个数。

示例

输入

n = 1

输出

5 6 7 8 9

解释

5! = 120

6!= 720

7! = 5040

8! = 40320

9! = 362880

可以观察到，所有输出数字的阶乘都有 n 个尾随零，即一个尾随零。

输入

n = 2

输出

10 11 12 13 14

解释

10! = 3628800

11! = 39916800

12! = 479001600

13! = 6227020800

14! = 87178291200

可以观察到，所有输出数字的阶乘都有 n 个尾随零，即两个尾随零。

输入

n = 5

输出

No Output

解释

25! = 15511210043330985984000000 有 6 个尾随零。

阶乘中恰好有 5 个尾随零的数字在其素数分解中将有 5 个因子 5，但不会有额外的因子 5。然而，素数分解中具有 5 个因子 5 的最小数字是 25!，其阶乘中有 6 个零。

朴素解法

我们简单地迭代一系列整数（1 到 106）。对于每个数字，我们检查其阶乘中零的个数是否等于给定的数字 n。如果是，我们将其添加到 ans 向量中。如果阶乘中的尾随零个数超过给定的数字 n，我们中断循环。

这种方法不适用于较大的数字，因为会发生溢出。

算法

阶乘函数 factorial(n)

Initialize fact = 1
for i = 2 to n:
   fact = fact * i
return fact

尾随零计数函数 count_trailing_zeros(num)

Initialize count = 0
while num % 10 = 0:
    count = count + 1
    num = num / 10
return count

查找具有 n 个尾随零的数字函数 find_numbers_with_n_trailing_zeros(n)

Initialize ans = empty vector
for i = 1 to 1e6:
    a = count_trailing_zeros(factorial(i))
    if a = n:
        ans.push_back(i)
    else if a > n:
        break
if size of ans = 0:
    print "No Output"
else:
    for x in ans:
       print x

时间和空间复杂度分析

时间复杂度：O(n*log n)

这段代码的时间复杂度为 O(n*log n)，因为 factorial() 函数的时间复杂度为 O(n)，并且在 for 循环中为 n 个值调用它，导致总时间复杂度为 O(n^2)。但是，如果尾随零的个数超过输入值 n，则循环会提前中断，这会大大减少迭代次数。

空间复杂度：O(n)

空间复杂度为 O(n)，因为程序使用向量来存储结果。

优化方法

该技术寻找阶乘中具有指定数量尾随零的所有数字。我们使用二分查找策略来找到具有指定数量尾随零的第一个数字，然后迭代所有后续具有相同数量尾随零的数字，直到找到一个没有 'n' 个尾随零的数字。

此方法包括以下步骤

• 定义一个函数 count_trailing_zeros()，它接受一个整数 num 并返回 num 阶乘中尾随零的个数。

• 定义一个函数 find_numbers_with_n_trailing_zeros()，它接受一个整数 n 作为输入并返回一个整数向量，这些整数的阶乘具有 n 个尾随零。

• 使用二分查找找到第一个具有 n 个尾随零的数字。

• 将开始后所有具有 n 个尾随零的数字推入 ans。

• 返回 ans。

算法

计算给定阶乘数 (num) 尾随零的函数

count = 0
while num > 0:
    num = num / 5
    count += num
return count

查找具有 n 个尾随零 (n) 的数字的函数

start = 0
end = maximum integer value
while start < end:
    mid = (start + end) / 2
    count = count_trailing_zeros(mid)
    if count < n:
        start = mid + 1
    else:
        end = mid
ans = empty vector
while count_trailing_zeros(start) == n:
    ans.push_back(start)
    start++
return ans

打印向量 (ans) 的函数

for i = 0 to ans.size():
print ans[i] + " "

主函数

n = 3
result = find_numbers_with_n_trailing_zeros(n)
print(result)

示例：C++ 程序

在下面的程序中，为了返回阶乘具有 'n' 个尾随零的数字，我们使用二分查找和素数因子的概念。其思想是考虑阶乘 n 的素数因子。尾随零总是由素数因子 2 和 5 产生的。可以很容易地观察到，素数因子中 2 的个数总是大于或等于 5 的个数。因此，如果我们计算素数因子中 5 的个数，我们可以找出尾随零的个数。然后，我们使用二分查找来确定阶乘中具有 'n' 个尾随零的数字。

// C++ program to find numbers which have ‘n’ trailing zeros in their factorial
#include <bits/stdc++.h>
using namespace std;
// function to count trailing zeros of the given factorial number
int count_trailing_zeros(int num){
    int count = 0;
    while (num > 0){
        num /= 5;
        count += num;
    }
    return count;
}
// function to find the number which have n trailing zeros
vector<int> find_numbers_with_n_trailing_zeros(int n){
    int start = 0;
    int end = INT_MAX;
    // binary search for first number with n trailing zeros
    while (start < end){
        int mid = (start + end) / 2;
        int count = count_trailing_zeros(mid);
        if (count < n)
            start = mid + 1;
        else
            end = mid;
    }
    // push all numbers after low with n trailing zeros.
    vector<int> ans;
    while (count_trailing_zeros(start) == n){
        ans.push_back(start);
        start++;
    }   
    return ans;
}
void print(vector<int> &ans){
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
}
// driver function
int main(){
    int n = 3;
    vector<int> result = find_numbers_with_n_trailing_zeros(n);
    print(result);
    return 0;
}

输出

15 16 17 18 19

时间和空间复杂度分析

时间复杂度：O(n)

代码的时间复杂度为 O(log n)，因为它使用二分查找来找到第一个具有 n 个尾随零的数字，这在每次迭代中都会将搜索空间减半。

空间复杂度：O(m)

空间复杂度为 O(m)，其中 m 是具有 n 个尾随零的数字的数量，因为程序将所有这些数字存储在向量中。

结论

本文讨论了两种查找阶乘末尾有 n 个零的数字的方法。为了更深入地理解，对这些方法的概念、示例、使用的算法、C++ 程序解决方案以及时间和空间复杂度分析进行了彻底的解释。