Question

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

Difficulty:Hard

Category:Binary-Search

Analyze

Solution

class Solution {
 public:
  int preimageSizeFZF(int K) { return int(getNumber(K) - getNumber(K - 1)); }

 private:
  long getNumber(int k) {
    long left = 0, right = LONG_MAX;
    while (left < right) {
      long mid = left + (right - left) / 2;
      long zeros = countZeros(mid);
      if (zeros <= k)
        left = mid + 1;
      else
        right = mid;
    }
    return left;
  }

  long countZeros(long num) {
    if (num < 5)
      return 0;
    else
      return num / 5 + countZeros(num / 5);
  }
};