Leetcode 793. Preimage Size of Factorial Zeroes Function

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이 있다.이 문제를 보고 이전의 비상식적인 2분 검색 방법을 생각해 보면 결과가 가능한 범위 내에서 조건을 충족시키는 최소값을 찾을 수 있습니다. 여기에는 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입니다. 물론 2분의 검색 범위를 수정할 수 있습니다. int64_t 유형은 다음과 같이 100.00%의 제출을 AC하고 격파할 수 있습니다.

 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로 검증할 수 있음)일 수 있기 때문에 이 범위 내에서 2분의 검색을 하면 된다. K=1의 경우 일단 5, 6, 7, 8, 9의 임의의 값을 검색하면 바로 되돌아갈 수 있고 검색이 끝나도 조건을 충족시키지 못한 값은 0으로 되돌아간다.이런 방법도 성형 과잉 문제를 피할 수 없지만 위의 무뇌이분 방법보다 합리적이라는 점에 주의해야 한다.
ps:이 문제는 직접 규칙을 찾는 방법으로 풀 수 있지만 알고리즘 문제로서 이런 순수한 관찰 방법으로 하는 것을 권장하지 않습니다.해답은 여기 있습니다.
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