Leetcode 793. Preimage Size of Factorial Zeroes Function

快来打我* 2021-12-21 02:11 120阅读 0赞

**Problem:**

Let `f(x)` be the number of zeroes at the end of `x!`. (Recall that `x! = 1 * 2 * 3 * ... * x`, and by convention, `0! = 1`.)

For example, `f(3) = 0` because 3! = 6 has no zeroes at the end, while `f(11) = 2` because 11! = 39916800 has 2 zeroes at the end. Given `K`, find how many non-negative integers `x` have the property that `f(x) = K`.

Example 1:
    Input: K = 0
    Output: 5
    Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.
    
    Example 2:
    Input: K = 5
    Output: 0
    Explanation: There is no x such that x! ends in K = 5 zeroes.

**Note:**

*  `K` will be an integer in the range `[0, 10^9]`.

**Solution**:

这道题很有意思，要求我们找出所有数字n的个数，使得n!结尾有K个0。看到这个问题，想到以前的非常规二分搜索方法，在结果可能的范围内查找满足条件的最小值，这里使用了Leetcode 172 Factorial Trailing Zeroes中的函数，然后在getMinimal函数中找到结尾有K个0的最小值，然后getMinimal(K+1)-getMinimal(K)即可。

1 class Solution {
     2 public:
     3     int trailingZeroes(int n) {
     4         int count_five = 0;  
     5         while(n > 0){  
     6             int k = n/5;  
     7             count_five += k;  
     8             n = k;  
     9         }  
    10         return count_five;    
    11     }
    12     int getMinimal(int K){
    13         int start = 0;
    14         int end = INT_MAX;
    15         while(start < end){
    16             int pivot = start+(end-start)/2;
    17             if(trailingZeroes(pivot) < K)
    18                 start = pivot+1;
    19             else
    20                 end = pivot;
    21         }
    22         return start;
    23     }
    24     int preimageSizeFZF(int K) {
    25         return getMinimal(K+1)-getMinimal(K);
    26     }
    27 };

然而这个算法却不能通过最后一个测试10^9，原因是结尾有10^9个0的最小值n！，其n已经大于INT\_MAX了，当然我们可以修改二分搜索范围，使用int64\_t类型即可AC并击败100.00%的提交，代码如下

1 class Solution {
     2 public:
     3     int64_t trailingZeroes(int64_t n) {
     4         int64_t count_five = 0;  
     5         while(n > 0){  
     6             int64_t k = n/5;  
     7             count_five += k;  
     8             n = k;  
     9         }  
    10         return count_five;    
    11     }
    12     int64_t getMinimal(int64_t K){
    13         int64_t start = 0;
    14         int64_t end = (int64_t)2*INT_MAX;
    15         while(start < end){
    16             int64_t pivot = start+(end-start)/2;
    17             if(trailingZeroes(pivot) < K)
    18                 start = pivot+1;
    19             else
    20                 end = pivot;
    21         }
    22         return start;
    23     }
    24     int64_t preimageSizeFZF(int64_t K) {
         25         return getMinimal(K+1)-getMinimal(K);
    26     }
    27 };

但是这样做未免有投机取巧之嫌，因此我们采用另一种更好的方法，不过这种方法需要一定的观察，我们发现，如果存在n使得n!末尾有K个0,那么答案必然是5（比如K为1,那么5,6,7,8,9均可，当n为10则会引入新的质因数5导致末尾有2个0）,如果根本不存在这样的n，那么结果是0,因此答案只有0和5两种可能。现在问题在于如果存在这样的n，n会在什么范围内。n的下限必然为K（观察可知末尾0的数量必然小于等于n），n的上限可以是5\*(K+1)（观察可知末尾有K个0的最大值必然小于等于5(K+1)，可以用上面的getMinimal验证），因此在这个范围内二分搜索即可，就K=1为例，一旦搜索到5,6,7,8,9中的任意值都可以直接返回，搜索结束还没有找到满足条件的值则返回0.注意即使是这种方法仍然无法避免整形溢出问题，但明显比上面那种无脑二分的方法合理。

ps:这道题还可以用直接找规律的方法解答，但作为一道算法题，不建议用这种纯观察的方法做。[解答在这里][Link 1]

**Code:**

1 class Solution {
     2 public:
     3     int trailingZeroes(int64_t n) {
     4         int64_t count_five = 0;  
     5         while(n > 0){  
     6             int64_t k = n/5;  
     7             count_five += k;  
     8             n = k;  
     9         }  
    10         return count_five;    
    11     }
    12     int preimageSizeFZF(int K) {
    13         int64_t start = K;
    14         int64_t end = (int64_t)5*(K+1);
    15         while (start < end) {
    16             int64_t pivot = start+(end-start)/2;
    17             int count = trailingZeroes(pivot);
    18             if (count == K) 
    19                 return 5;
    20             else if (count < K) 
    21                 start = pivot + 1;
    22             else 
    23                 end = pivot;
    24         }
    25         return 0;
    26     }
    27 };

转载于:https://www.cnblogs.com/haoweizh/p/10359138.html

[Link 1]: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/discuss/117631/C++-O%28logn%29-math-solution-with-explanation