This is the 12th day of my participation in the First Challenge 2022

The title

793. K zeros after the factorial function

parsing

Think about it, how do I get a 10 in multiplication?

  • Or a number that is itself a multiple of 10.
  • It’s either a multiple of 5 times a multiple of 2.

So, let’s analyze the topic with this in mind:

  • In other words, if you encounter a multiple of 5, you must find a multiple of 2 (and not a multiple of 10), and the 5 will make up a multiple of 10. Also, the latter result will only be greater than or equal to the previous result.

In other words:

  • Suppose y = x + 5, then f (x) = f (x + 1) = f (x + 2) = f (x + 3) = f (x + 4) = f (y) – m, including 5 m ^ ^ = y. [1]

K = 5 is 0 because there is a 25 in the middle, so there are no 5 consecutive 0’s.

So, looking at the K given by the problem, our function is F, (the corresponding function is W(x), that is, the number of zeros after x factorial) then there must be:

  • F(K) = 0 or F(K) = 5(inferred from [1])

So, how do we deduce which K’s are zero?

According to [1], it can be known that:

  • If you have a situation where you can split out multiple 5’s, where W of x minus W of x minus 1 is greater than 1, then all of these k’s between W of x minus 1 and W of x are going to be 0.

And since every 0 contains a 5, K 0’s must be composed of exactly K 5’s.

So, the question becomes:

  • Is it possible to find a number where all the numbers up to some number contain exactly K 5’s? If it does, it’s 5; If it doesn’t, then it’s 0.

And: 5 * K! In, there must be greater than or equal to K 5’s.

So, a simple way to do this is to go from 5 times K factorial. So let’s start by doing K minus =5 every time, to see if we have exactly W of x is equal to K.

Because we know that from K to K minus 5, once and only once, F of X will add a number greater than 1; Otherwise, it’s +1; And based on that, we can look at each interval of length 5 and see if K is going to be included in the interval.

So, how to quickly determine W (x) can refer to the following question.

Subproblem: factorial 0

The title

Leetcode-cn.com/problems/fa…

parsing

According to the above analysis, for any x, we can quickly divide x by 5 to figure out how many 5’s x can extract. These 5’s are the number of 5’s that can be extracted from 1 to x.

public static int trailingZeroes(int n) {
    if(n<5) return 0;
    return n/5 + trailingZeroes(n/5);
}
Copy the code

The simplest answer can be drawn:

public static int preimageSizeFZF(int k) {
    long y = 5*k;
    while(true) {long m = trailingZeroes(y);
        if(m>k) {
            y -=5;
            continue;
        }
        if(m == k) return 5;
        if(m < k) return 0; }}public static long trailingZeroes(long n) {
    if(n<5) return 0;
    return n/5 + trailingZeroes(n/5);
}
Copy the code

And then I ran out of time.

The last input to be executed:

24397491

Think about it:

  • In this algorithm, do WE need to evaluate everything from 0 to 5K?

    Of course the answer is no, so how do we determine the lower bound?

    According to the trailingZeroes method above, we know:

    W(x) = sum(x/5 + x/25 + … + 1), according to the sum formula of geometric sequence:

W(x) =x/ 5 * (1-(1/5)^n^)/(1-1/5) => W(x)>=x/4.

In other words, the lower bound is actually 4X: the number that satisfies the problem must be between 4X and 5x.

So if you end up with y less than or equal to 4x you know that there’s no such number.

And, in fact, since the final function is a function that increases with n, you can use dichotomy to determine whether this number exists or not.

The reason we can use dichotomy here is that the return condition of 5 is that our value meets the condition.

So there’s a little bit of a trap here, int * long in Java, and the answer is going to be in the int range, so you have to make sure that when you multiply, the multipliers are all of type long.

The final answer is clear:

public static int preimageSizeFZF(int k) {
    long r = 5L*k,l = 4L*k+1L;
    while(l<=r){
       long mid = (l+r)/2;
       long n = trailingZeroes(mid);
       if(n == k) return 5;
       if(n > k) r = mid-1;
       else l = mid+1;
    }
    return trailingZeroes(l)==k?5:0;
}

public static long trailingZeroes(long n) {
    if(n<5) return 0;
    return n/5 + trailingZeroes(n/5);
}
Copy the code

Execution time: 0 ms, beating 100.00% of users in all Java commits

Memory consumption: 35.1 MB, beating 69.55% of all Java commits