Last updated on January 29th, 2025 at 02:15 am

Here, we see a Preimage Size of Factorial Zeroes Function LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Brainteaser

Level of Question

Hard

Preimage Size of Factorial Zeroes Function LeetCode Solution

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

2. Coding Pattern Used in Solution

The provided code in all languages uses a Modified Binary Search pattern to solve the problem. The goal is to find the number of integers x such that the factorial of x has exactly k trailing zeroes. The binary search is modified to work on the range of possible values of x and uses a helper function to calculate the number of trailing zeroes for a given number.

3. Code Implementation in Different Languages

3.1 Preimage Size of Factorial Zeroes Function 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);
  }
};

3.2 Preimage Size of Factorial Zeroes Function 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.3 Preimage Size of Factorial Zeroes Function 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;
};

3.4 Preimage Size of Factorial Zeroes Function 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  

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log(k) * log(k))	O(log(k))
Java	O(log(k) * log(k))	O(log(k))
JavaScript	O(log(k) * log(k))	O(1)
Python	O(log(k) * log(k))	O(1)

• Time Complexity:
  • The binary search runs in O(log(k)) because the search space is halved in each iteration.
  • The helper function (trailingZeroes or helper) runs in O(log(k)) because it iterates over powers of 5.
  Thus, the overall time complexity is O(log(k) * log(k)).
• Space Complexity:
  • In C++ and Java, the recursive implementation of trailingZeroes uses O(log(k)) space for the recursion stack.
  • In JavaScript and Python, the iterative implementation avoids recursion, so the space complexity is O(1).
• Modified Binary Search:
  • The binary search is modified to work on a mathematical property (number of trailing zeroes) rather than directly searching for a value in an array.