Question

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 1

class Solution:
  def preimageSizeFZF(self, k: int) -> int:
    def f(x):
      if x == 0:
        return 0
      return x // 5 + f(x // 5)

    def g(k):
      return bisect_left(range(5 * k), k, key=f)

    return g(k + 1) - g(k)

class Solution {
  public int preimageSizeFZF(int k) {
    return g(k + 1) - g(k);
  }

  private int g(int k) {
    long left = 0, right = 5 * k;
    while (left < right) {
      long mid = (left + right) >> 1;
      if (f(mid) >= k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return (int) left;
  }

  private int f(long x) {
    if (x == 0) {
      return 0;
    }
    return (int) (x / 5) + f(x / 5);
  }
}

class Solution {
public:
  int preimageSizeFZF(int k) {
    return g(k + 1) - g(k);
  }

  int g(int k) {
    long long left = 0, right = 1ll * 5 * k;
    while (left < right) {
      long long mid = (left + right) >> 1;
      if (f(mid) >= k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return (int) left;
  }

  int f(long x) {
    int res = 0;
    while (x) {
      x /= 5;
      res += x;
    }
    return res;
  }
};

func preimageSizeFZF(k int) int {
  f := func(x int) int {
    res := 0
    for x != 0 {
      x /= 5
      res += x
    }
    return res
  }

  g := func(k int) int {
    left, right := 0, k*5
    for left < right {
      mid := (left + right) >> 1
      if f(mid) >= k {
        right = mid
      } else {
        left = mid + 1
      }
    }
    return left
  }

  return g(k+1) - g(k)
}