<p>Let <code>f(x)</code> be the number of zeroes at the end of <code>x!</code>. Recall that <code>x! = 1 * 2 * 3 * ... * x</code> and by convention, <code>0! = 1</code>.</p>

<ul>
	<li>For example, <code>f(3) = 0</code> because <code>3! = 6</code> has no zeroes at the end, while <code>f(11) = 2</code> because <code>11! = 39916800</code> has two zeroes at the end.</li>
</ul>

<p>Given an integer <code>k</code>, return the number of non-negative integers <code>x</code> have the property that <code>f(x) = k</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> k = 0
<strong>Output:</strong> 5
<strong>Explanation:</strong> 0!, 1!, 2!, 3!, and 4! end with k = 0 zeroes.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> k = 5
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no x such that x! ends in k = 5 zeroes.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> k = 3
<strong>Output:</strong> 5
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def preimageSizeFZF(self, k: int) -> int:
        # Helper function to calculate number of trailing zeroes in x!
        def f(x):
            count = 0
            while x > 0:
                x //= 5
                count += x
            return count
        
        # Binary search to find the lower bound where f(x) == k
        def binary_search_lower(k):
            left, right = 0, 5 * (k + 1)
            while left < right:
                mid = (left + right) // 2
                if f(mid) < k:
                    left = mid + 1
                else:
                    right = mid
            return left
        
        # Binary search to find the upper bound where f(x) == k
        def binary_search_upper(k):
            left, right = 0, 5 * (k + 1)
            while left < right:
                mid = (left + right) // 2
                if f(mid) <= k:
                    left = mid + 1
                else:
                    right = mid
            return left - 1
        
        # Find the lower and upper bounds
        lower = binary_search_lower(k)
        upper = binary_search_upper(k)
        
        # If there is no x such that f(x) == k, return 0
        if f(lower) != k:
            return 0
        return upper - lower + 1
16400