preface

The first is based on the fact that we can’t really put n! Then count how many zeros there are at the end of the result; It’s good that n is small, but if n is large, or even approaches infinity, we can’t do that. There are two main reasons:

  1. General computer computing capacity and storage capacity is also limited, is unable to calculate such a large number.
  2. Even if a computer could do it, doing so would be time-consuming and could take a long time.

Even the computer can’t figure it out, so what do we do? Don’t panic. We can’t figure it out directly, but we can take it apart step by step.

Dismantling ideas

First of all, we want to know under what circumstances can a 0 be generated?

Well, if you multiply a number by 10, you get an extra 0 at the end. 10 is 5 times 2.

The number of zeros at the end of a multiplication of numbers depends on the number of pairs of 5 and 2 factors that result from the factorization.

For n! So here’s the fact that when you factor the numbers you multiply, the number of 2’s is definitely greater than the number of 5’s.

So, the problem can be broken down to: just find the number of factors of 5 after the factorization, the number of 5 is the number of zeros at the end.

Solution 1: direct method

The idea of this solution is: directly add n! For each number in, factor it by 5, and finally add up the number of 5’s that occur.

public int calculateZeroInFactorial(int n) {
  int count = 0;
  // Loop through all the multipliers
  for (int i = n; i > 0; i++) {
    if (i % 5= =0) {
      // If the multiplier factorizes 5, see how many 5s this multiplier factorizes
      int a = i;
      while(a % 5= =0) {
        a = a / 5; count++; }}}return count;
}
Copy the code

But this algorithm is order nlog of n, so is there a faster algorithm?

Solution two: log(n) solution

Analysis:

  1. n! For every five of these multipliers, there must be at least one factor of five. So n over 5 is equal to at least the number of 5’s that can occur.
  2. It says at least, since n over 5 doesn’t have the exact number of 5 factors, for example, if 25 is equal to 5 times 5, if you factor it into 5, that’s the same thing as two 5 factors, and you already counted one of them when you divided by 5 in the first step, So it’s going to be 5 more than it was before.
  3. And so on, the factor that can be factored out by 25 times 5 is 125 is equal to one more factor of 5 than the previous factor of 25. The factor that can be factored 125 times 5 is 625 has one more factor of 5 than the factor of 125. And 625 times 5… .

So, n! How many 5-factors can the result of?

N /5 + n/25 + N /125 + n/625 +… .

Such as 128! How many zeros do I have at the end of the factorial of theta?

128/5 +128/25 + 128/125 = 25+5+1 = 31 PCS

Such as: 1247! How many zeros do I have at the end of the factorial of theta?

1247/5 + 1247/25 + 1247/125 + 1247/625 = 249+49+9+1 = 308

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

This algorithm is O(log(n)) in time, much more efficient, and requires only a few lines of code.