793. Preimage Size of Factorial Zeroes Function

2950 단어 leetcode
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].
class Solution(object):
    def calcFactorial(self,v):
        n = v
        count = 0
        while n > 0:
            count += n / 5
            n = n / 5
        return count

    def preimageSizeFZF(self, K):
        high = K*5
        low = 0
        while low <= high:
            mid = (high + low)/2
            if self.calcFactorial(mid) < K:
                low = mid +1
            elif self.calcFactorial(mid) > K:
                high = mid - 1
            else:
                return 5
        return 0

좋은 웹페이지 즐겨찾기