793. Preimage Size of Factorial Zeroes Function

Description

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

 

Solutions

Solution: Binary Search

• Time complexity: O(log5k)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} k
 * @return {number}
 */
const preimageSizeFZF = function (k) {
  let left = 0;
  let right = (k + 1) * 5;

  const getZeroesCount = num => {
    let result = 0;

    while (num) {
      num = Math.floor(num / 5);
      result += num;
    }
    return result;
  };

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const count = getZeroesCount(mid);

    if (count === k) return 5;
    count > k ? (right = mid) : (left = mid + 1);
  }
  return 0;
};