Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

Yesterday’s question was medium, I had some trouble yesterday and didn’t have time to do the daily question, so I will make up for it today. The question yesterday is mainly about the exercise of mathematical thinking, so I have to look for useful information through the question to solve the question better

A daily topic

Yesterday’s question was 172. Zero after factorial. The difficulty was medium

  • Given an integer n, return n! The number of trailing zeros in the result.

  • Tip n! = n * (n – 1) * (n – 2) * … Times 3 times 2 times 1

 

Example 1:

Enter n =3Output:0Explanation:3! = 6, not including trailing0
Copy the code

Example 2:

Enter n =5Output:1Explanation:5! = 120There is a tail0
Copy the code

Example 3:

Enter n =0Output:0
Copy the code

 

Tip:

  • 0 <= n <= 104

Advancements: Can you design and implement logarithmic time complexity algorithms to solve this problem?

Answer key

Mathematics method

Since the problem is the factorial, there is no way to use the brute force method to calculate, because the factorial can easily break the upper limit of the number, so what we have to do is to find the law

First of all, let’s see why there’s a 0 at the end of a factorial, because anything times 10 has a 0 at the end, so it’s only going to be multiplied by 10, multiplied by 20 and you can see that 2 times 10 is always multiplied by 10.

Then 10 can be viewed as 2 * 5, and let’s take a hierarchy of 5 to demonstrate: 5 * 4 * 3 * 2 * 1. So that’s the level of 5, so how many zeros are there — 120 zeros because there’s a pair of 5 times 2, and whether you use 2 times 5 or 4 times 5, you’re only going to get a pair, because the number of 5 is much smaller than the number of 2

Here thinking is clear, we require several zero behind the class, is to ask the class of several multiples of 5, like 25 can break down to 5 * 5 2 that is zero, and so on, we need to find the current class, there are a few number can be broken down to 5, they can break down a few respectively, And then you add them up, and you get the answer you need.

And now let’s take 125 for example, in the factorial of 125, there will be 25 multiples of 5 like 5, 10, 15, 20, and there will be two 5 times 5, which is a multiple of 25, for example, 25 will provide two 5’s, So there are five of 125 factorial that will provide two 5’s, so it’s 25 plus 5. And then finally, we have 125, which is equal to 5 times 5 times 5 and it’s going to provide three fives, so it’s going to be 25 plus 5 plus 1, so we can figure out that 125 factorial is going to be followed by 31 0’s.

We then translate the above ideas into code

The first time you divide by 5 is the same as the first calculation of 125 above, and you figure out how many numbers can provide a 5. The second time you divide by 5 is the same as counting the number that provides two 5’s, and so on, until you know that n and you can’t divide by 5. I can figure out how many 5’s I can supply.

/ * * *@param {number} n
 * @return {number}* /
 var trailingZeroes = function(n) {
    let res = 0;
    while(n ! = =0) {
        n = Math.floor(n / 5);
        res += n;
    }
    return res;
};
Copy the code