Writing in the front

Feel good writing, harvest, remember to click attention and click a thumbs-up, very grateful. I feel it, like this is purely mathematical analysis problem, I will record it down and give you time to let you to analyze this problem, may can be analyzed, but limit your time to let you solve, very easy to get stuck, so met the learning mentality, then later if encounter similar problems, so it is very quick and agile.

Problem description

Problem solving

You can’t rely on the factorial to figure out how many zeros there are, because it’s easy to overspill factorials, so let’s just think about it step by step. How many zeros do you have at the end? You just multiply the current number by a 10 to add a 0.

And then specifically for 5! So 5 * 4 * 3 * 2 * 1 = 120, and we find that there is a 0, because 2 and 5 make a 10. And for 10, there’s really only 2 times 5, so we just have to figure out how many pairs of 2/5 there are. Let’s factor each of these multipliers a little bit more. Let’s look at an example.

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 
= 
11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1
Copy the code

1 * 2, 2 * 2, 3 * 2, 4 * 2… . For factors of 5, 1 * 5, 2 * 5… . Factors with 2 occur every two times, factors with 5 occur every five times, and all 2 occur in far more numbers than 5. In other words, if you find a 5, you’re bound to find a 2 that matches it. So we just have to find how many 5’s there are. We just have to figure out how many factors of 5 there are in each multiplicative number.

public int trailingZeroes(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int N = i;
        while (N > 0) {
            if (N % 5= =0) {
                count++;
                N /= 5;
            } else {
                break; }}}return count;
}
Copy the code

However, the above idea is not the optimal idea, we can further optimize it. For a factorial of a number, as we analyzed before, the factor of 5 must occur every fifth number, which is n factorial. = 1 * 2 * 3 * 4 * (1 * 5) *… * (2 * 5) *… * (3 * 5) *… * n. Because every fifth number has a 5, so to figure out how many 5’s there are, we just need n over 5 to figure it out.

But it’s not over yet. Keep analyzing. . * (1 * 5) *… * (1 * 5 * 5) *… * (2 * 5 * 5) *… * (3 * 5 * 5) *… * n. Every 25 numbers, we have two 5’s, so in addition to counting every fifth number as a 5, every 25 numbers, we have to count another 5. So we’re going to have to add n over 25 5’s.

And we also see that every 5 times 5 times 5 is 125, we have 3 5’s, so we have to add n over 125. So the pattern is that every five numbers have a five, every 25 numbers have two fives, every 125 numbers have three fives… And so on. The final number of 5 is n / 5 + n / 25 + n / 125… . If you write a program, if you just follow the formula up here, the denominator might overflow. So when we do n over 25, we update the n, n is equal to n over 5, and then we compute n over 5. Same thing here.

public int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        count += n / 5;
        n = n / 5;
    }
    return count;
}
Copy the code