Skip to content

Latest commit

 

History

History
 
 

793. Preimage Size of Factorial Zeroes Function

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

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].

Companies:
Amazon

Solution 1.

// OJ: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
// Author: github.com/lzl124631x
// Time: O((logK)^2)
// Space: O(1)
class Solution {
private:
    int getZeros(int i) {
        int ans = 0;
        while (i) {
            ans += i;
            i /= 5;
        }
        return ans;
    }
public:
    int preimageSizeFZF(int K) {
        if (!K) return 5;
        int i = 1;
        while (getZeros(i) < K) i *= 5;
        int L = i / 5, R = i;
        while (L <= R) {
            int M = (L + R) / 2;
            int z = getZeros(M);
            if (z == K) return 5;
            if (z < K) L = M + 1;
            else R = M - 1;
        }
        return 0;
    }
};