Preimage Size of Factorial Zeroes Function in Java

Ah, the Preimage Size of Factorial Zeroes Function! Sounds fancy, right? It’s like the math equivalent of trying to find your lost socks in the laundry—frustrating, yet oddly satisfying when you finally figure it out. So, what’s the deal? You’re tasked with finding how many non-negative integers x exist such that the number of trailing zeroes in x! (that’s factorial, not a typo) is exactly k.

Imagine you’re baking a cake and you want to know how many eggs you need. But instead of eggs, you’re counting trailing zeroes. Because, you know, that’s what every baker dreams of doing!

Language Links

Code Solution


class Solution {
  public int preimageSizeFZF(int k) {
    long l = 0;
    long r = 5 * (long) k;

    while (l < r) {
      final 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 : (int) (n / 5 + trailingZeroes(n / 5));
  }
}

Approach Explanation

The code uses a binary search approach to find the number of integers x such that the trailing zeroes in x! equals k. The trailingZeroes function calculates the number of trailing zeroes in a factorial by counting how many times 5 can be factored out of the numbers leading up to n. This is because trailing zeroes are produced by pairs of 2 and 5, and there are always more 2s than 5s in factorials.

Binary Search: The search space is defined between 0 and 5 * k. The midpoint m is calculated, and the number of trailing zeroes for m is checked.
Adjusting Search Space: If the trailing zeroes are greater than or equal to k, the right boundary is adjusted. Otherwise, the left boundary is moved up.
Final Check: After the loop, if the trailing zeroes at l equal k, it returns 5, indicating there are five integers that satisfy the condition. If not, it returns 0.

Time and Space Complexity

Time Complexity: O(log(k)), since we are performing a binary search.
Space Complexity: O(1), as we are using a constant amount of space.

Real-World Example

Let’s say you’re at a party, and you want to know how many people can bring a dessert that has exactly k layers of chocolate. Each layer of chocolate represents a trailing zero in the factorial world. You start asking around, and after some binary searching through the crowd (or maybe just asking your friends), you find out that there are exactly 5 people who can bring a dessert with k layers. Voilà! You’ve solved the problem!