LeetCode - Algorithms - 793. Preimage Size of Factorial Zeroes Function

Problem

793. Preimage Size of Factorial Zeroes Function

Relevant problem

An easy problem as 172. Factorial Trailing Zeroes and its solutions: https://hezhigang.github.io/2020/06/06/LeetCode-Algorithms-factorial-trailing-zeroes/

Java

Binary Search strategy

Binary search, also known as half-interval search, logarithmic search, or binary chop, is a general algorithm for linearly ordered data structure, and There are numerous variations of binary search.

Let \( f(x) \) be the number of zeroes at the end of \(x!\). We can observe that \( f(x) \) rise when \( x \equiv 0 \hspace{2mm} (mod \hspace{1mm} 5) \),
and \( f(5k)=f(5k+1)=f(5k+2)=f(5k+3)=f(5k+4) \).
\( f(x)=\lfloor \frac{x}{5} \rfloor + \lfloor \frac{x}{25} \rfloor + \cdots + \lfloor \frac{x}{5^n} \rfloor \) where \( \lfloor \frac{x}{5^n} \rfloor \geq 1 \)
This geometric sequence with common ratio \( r = \frac{1}{5} \) has a limit that can be computed from the finite sum formula \( \sum_{k=1}^{\infty} \frac{x}{5^k} = \lim_{n \to \infty}\sum_{k=1}^{n} \frac{x}{5^k} = \frac{\frac{x}{5}}{1-\frac{1}{5}} = \frac{x}{4} \), so, there is a inequality that \( \frac{x}{5} < f(x) < \frac{x}{4} \), which gives a small upper and lower bound for binary search algorithm.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int preimageSizeFZF(int K) {
        int count = 0;
        long r = search_rank(K);
        count = r==-1?0:5;
        return count;
    }
    
    private long search_rank(long K) {
        long lo = 4*K;
        long hi = 5*K;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long y = f(mid);
            if (K < y)
                hi = mid - 1;
            else if (K > y)
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }

    private long f(long x) {
        long count = 0;
        for (long i = 5; i <= x; i *= 5)
            count += x / i;
        return count;
    }
}

Submission Detail

  • 44 / 44 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.
  • Memory Usage: 35.6 MB, less than 100.00% of Java online submissions for Preimage Size of Factorial Zeroes Function.

Complexity Analysis

Time Complexity

\( O(NlogN) \) where N is the input integer such that \( f(x)=N \)

Space Complexity

\( O(1) \) as there is no extra space other than local varibles.