Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/793.html

793. Preimage Size of Factorial Zeroes Function (Hard)

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

Companies:
Amazon

Solution 1.

• Java
• C++
• Python
• Go

• class Solution {
      public int preimageSizeFZF(int K) {
          long low = 0, high = (long) K * 5;
          while (low <= high) {
              long mid = (high - low) / 2 + low;
              long endZeroes = endZeroes(mid);
              if (endZeroes == K)
                  return 5;
              else if (endZeroes > K)
                  high = mid - 1;
              else
                  low = mid + 1;
          }
          return 0;
      }
  
      public long endZeroes(long num) {
          long zeroes = 0;
          while (num > 0) {
              num /= 5;
              zeroes += num;
          }
          return zeroes;
      }
  }
  
  ############
  
  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);
      }
  }
  

• // OJ: https://leetcode.com/problems/preimage-size-of-factorial-zeroes-function/
  // Time: O((logK)^2)
  // Space: O(1)
  class Solution {
  private:
      int getZeros(int i) {
          int ans = 0;
          while (i) {
              ans += i;
              i /= 5;
          }
          return ans;
      }
  public:
      int preimageSizeFZF(int K) {
          if (!K) return 5;
          int i = 1;
          while (getZeros(i) < K) i *= 5;
          int L = i / 5, R = i;
          while (L <= R) {
              int M = (L + R) / 2;
              int z = getZeros(M);
              if (z == K) return 5;
              if (z < K) L = M + 1;
              else R = M - 1;
          }
          return 0;
      }
  };
  

• 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)
  
  
  

• 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)
  }
  

All Problems

All Solutions