Algorithm

Problem Name: 793. Preimage Size of Factorial Zeroes Function

Problem Link: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
 

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 two zeroes at the end.

Given an integer k, return the number of 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.

Example 3:

Input: k = 3
Output: 5

 

Constraints:

  • 0 <= k <= 109

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const preimageSizeFZF = function(K) {
  let last = 1
  while (last < K) last = last * 5 + 1
  while (last > 1) {
    K %= last
    if (last - 1 == K) return 0
    last = ((last - 1) / 5) >> 0
  }
  return 5
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
k = 0

Output

x
–
+
cmd
5

#2 Code Example with Python Programming

Code - Python Programming


class Solution:
    
    def count(self, num):
        cnt = 0
        while num:
            cnt += num // 5
            num //= 5
        return cnt 
    
    def preimageSizeFZF(self, K):
        l, r = 0, 2 ** 63 - 1
        while l < r:
            mid = (l + r) // 2
            if self.count(mid) < K:
                l = mid + 1
            else:
                r = mid
        return 5 - (l % 5) if self.count(l) == K else 0
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
k = 0

Output

x
–
+
cmd
5
Advertisements

Demonstration

Previous
#792 Leetcode Number of Matching Subsequences Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#794 Leetcode Valid Tic-Tac-Toe State Solution in C, C++, Java, JavaScript, Python, C# Leetcode