Preimage Size of Factorial Zeroes Function Solution in C++

Navigate to Other Solutions

Problem Description

The Preimage Size of Factorial Zeroes Function is a mathematical problem that asks: “How many numbers can you feed into a function that counts trailing zeroes in factorials, such that the output is exactly k?”

Imagine you’re baking a cake and you want to know how many eggs you can crack before you run out of space in your mixing bowl. The more eggs you crack (or numbers you input), the more likely you are to end up with a mess (or trailing zeroes). The challenge is to find out how many eggs (or numbers) you can crack before you hit that sweet spot of exactly k trailing zeroes.

Code Solution


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

Approach

The approach taken in this solution is a binary search method. The idea is to find the smallest number m such that the number of trailing zeroes in m! is at least k. The function trailingZeroes counts how many trailing zeroes are in the factorial of a number by counting the number of times 5 can be factored out (because 2s are more abundant). If the number of trailing zeroes equals k, we return 5, indicating there are exactly five numbers that produce k trailing zeroes.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log(k))
Space Complexity	O(1)

Real-World Example

Think of it this way: you’re at a party, and you want to know how many people can fit in a room before it gets too crowded (or before the trailing zeroes start piling up). You start counting, but you can only see the people who are standing in a certain way (like how trailing zeroes only appear under specific conditions in factorials). The solution helps you figure out how many people (or numbers) can fit in the room (or produce k trailing zeroes) without causing a ruckus.