Last updated on October 9th, 2024 at 06:24 pm

Here, We see Preimage Size of Factorial Zeroes Function LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Preimage Size of Factorial Zeroes Function LeetCode Solution

Problem Statement

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

1. Preimage Size of Factorial Zeroes Function Leetcode Solution C++

class Solution {
 public:
  int preimageSizeFZF(int k) {
    long l = 0;
    long r = 5L * k;
    while (l < r) {
      const long m = (l + r) / 2;
      if (trailingZeroes(m) >= k)
        r = m;
      else
        l = m + 1;
    }
    return trailingZeroes(l) == k ? 5 : 0;
  }
 private:
  int trailingZeroes(long n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
  }
};

2. Preimage Size of Factorial Zeroes Function Leetcode Solution Java

class Solution {
    public int preimageSizeFZF(int k) {
        return (int)(rightBoundOfKTrailingZeros(k) - leftBoundOfKTrailingZeros(k) + 1);
    }
    private long leftBoundOfKTrailingZeros(int k) {
        long start = 0;
        long end = 5L * (k + 1);
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if (trailingZeroes(mid) < k) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (trailingZeroes(start) == k) {
            return start;
        } else {
            return end;
        }
    }
    private long rightBoundOfKTrailingZeros(int k) {
        long start = 0;
        long end = 5L * (k + 1);
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            if (trailingZeroes(mid) <= k) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (trailingZeroes(end) == k) {
            return end;
        } else {
            return start;
        }
    }
    private int trailingZeroes(long n) {
        int result = 0;
        long divisor = 5;
        while (divisor <= n) {
            result += n / divisor;
            divisor *= 5;
        }
        return result;
    }
}

3. Preimage Size of Factorial Zeroes Function Leetcode Solution JavaScript

var helper = function(m) {
    let r = m;
    while(m > 0) {
        m = Math.floor(m / 5);
        r += m;
    }
    return r;
}
var preimageSizeFZF = function(k) {
    let min = 0, max = k+1;
    while(min < max) {
        let center = ~~((min+max)/2);
        let zero = helper(center);
        if (zero > k) {
            max = center;
        }
        else if (zero < k) {
            min = center + 1;
        }
        else {
            return 5;
        }
    }
    return 0;
};

4. Preimage Size of Factorial Zeroes Function Solution Python

class Solution(object):
    def preimageSizeFZF(self, k):
        m = floor(log(4 * k + 1, 5))
        while m:
            unit = (5 ** m - 1) // 4
            if k
                return 0
            k %= unit
            m -= 1
        return 5