Preimage Size of Factorial Zeroes Function


  • 0

    Click here to see the full article post


  • 0
    W

    I think you are trying to explain it, but I can't absorb why zeta can be computed without ever taking a factorial, and without modulo 10 to check for trailing zeros.


  • 1
    S

    @wilderfield Imagine an expression for n! = 1 * 2 * 3 * ... * n, zeroes are all produced by multiplying 2s and 5s which are in its factorization, therefore if we count the number of 2s and number of 5s and take the minimum we'll have the number of zeroes at the end. Again, notice that every kth number in n! expression can be divided by k, therefore there are floor(n/k) such numbers. Same is true for n/k^2 and so on until n/k^i > n.
    Using that we can count the number of 2s and 5s as it's described in the solution, one small point to notice is that every number that can be divided by 2^i only contributes 1 to the count of 2s as we have counted the other i - 1 contributions in previous steps.


  • 1
    Z

    How do you know the range is [K, 10*K+1]?


  • 0

    @zixuan_wang x/5 <= zeta(x) <= x.


  • 0
    J

    I wondered since x/5 <= zeta(x) <= x based on @awice solution, shouldn't x be from K to 5K + 1? i.e. lo = K, hi = 5K + 1 (zeta(x) = K = x/5 plus some positive value, so x here should not be great than 5K.)

    Another question is does hi = 5(or 10) * K + 1 applies to general cases other than K = 0? I know that for case K = 0, hi needs to be different from lo so the loop can be executed. Are there any other cases that mi actually is the corner case mi = 5(or 10) * K + 1? Thank you!


  • 0
    A

    @awice
    I have a different solution for this, one without recursion. It is a mathematical solution of sorts.

    So we know that the number of zeroes in x! is [x/5**1] + [x/5**2] + ... + [x/5**n] .. (1)
    The number of zeroes can't exceed the maximum value of K, that is 10**9
    log 10**9 to the base 5 is 13, so the maximum value of n in (1) is 13.

    So now, we need to find all values of x (if exists) for which:
    [x/5**1] + [x/5**2] + ... + [x/5**13] = K .. (2)

    (2) can be rewritten as:
    (5**12)x + (5**11)x + ... x = K*(5**13)
    Solving for x, we have x = K*(5**13)//305175781

    This is the lowest possible value that x could take. The highest value could be x+4 since there's guaranteed to be a number divisible by 5 in 5 consecutive numbers.

    Now we just check the number of zeros in x, x+1, x+2, x+3 and x+4. If the number of zeroes in any of the cases is equal to K, we can add this to a counter. If the number of zeroes ever exceeds K, we can terminate since the number of zeroes will only increase.

    Here's my python code, with the class and function definition removed for brevity:

            if K==0:
                return 5
            
            def zc(n):
                r,c = 0,1
                while True:
                    x = n//5**(c)
                    if x > 0:
                        r += x
                    else:
                        return r
                    c+=1
            
            start = K*(5**13)//305175781
            s = 0
            
            for i in range(start, start+5):
                t = zc(i)
                if t == K:
                    s+=1
                if t > K:
                    break
                    
            return s
    

    This is the first time I've submitted a solution so please let me know if something isn't easily understandable. Thanks!


  • 0

    @jun1013 We can establish 5K+1, or even better bounds -- it doesn't matter that much for our binary search.


  • 0
    S

    Great article, just one thing, the range of K is [0, 10^9], with this range, the current hi will overflow, shall we make it become long instead?


  • 0
    S

    @awice
    Great solution!But when the input=10^9,your method will fail.The answer is 5 but your output is 0.How to solve this?Thanks!


  • 0
    S

    @sdyjf, use long instead of int to do all calculations


  • 0
    J

    How does this solution handle the case where x needs to be larger than Integer.MAX_VALUE in Java so that zeta(x) = K? For example when K = 10^9.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.