preface

It’s five thirty! Have you finished writing HXDM’s requirements this week? Have you decided what you want for dinner?

If you don’t think well, let’s see the solution!

Topic describes

172. Zero after factorial

Given an integer n, return n! Result the number of zeros in the mantissa.

Example 1:

Input: 3 Output: 0 Explanation: 3! = 6. There are no zeros in the mantissa.Copy the code

Example 2:

Input: 5 Output: 1 Explanation: 5! = 120, with one zero in the mantissa.Copy the code

Note: The time complexity of your algorithm should be O(log n).

Their thinking

Given an integer n, find the number of zeros in the result after n factorial.

Let’s first understand what a factorial is:

Factorial is a mathematical term invented by Christian Kramp (1760 ~ 1826) in 1808. The factorial of a positive integer (factorial) is the product of all positive integers less than or equal to that number, and 0 factorial is 1. The factorial of the natural number n is written as n! . This notation was introduced by Keith Karman in 1808. That is, n! = 1 x 2 x 3 x… * n (n – 1). Factorial can also be defined recursively: 0! = 1, n! =(n-1)! X n.

factorial

So in 0 minus 9 we only have 2 x 5 = 10, so what does that mean?

That means if you have a pair of 2’s and 5’s, you get an extra 1 and a 0. If you don’t know, let’s do it this way:

// 1 factorial 1 = 1 // 2 factorial 1x2 = 2 // 3 factorial 1x2x3 = 6 // 4 factorial 1x2x3x4 = 24 // how many zeros does the factorial of 5 have? 1x2x3x4x5 = 120 // There is 1 0 // 6 factorial 1x2x3x4x5x6 = 720 // 7 factorial 1x2x3x4x5x6x7 = 5040 // how many mantras of 8 are 0 1x2x3x4x5x6x7x8 = 40320 // 9 factorial 1x2x3x4x5x6x7x8x9 = 362880 // 10 factorial 1x2x3x4x5x6x7x8x9x10 = 3628800Copy the code

The factorial of 5 has two pairs of 2 and 5 and the factorial of 10 has two pairs of 2 and 5(multiples of 2 are 2, 4, 6, 8, 10 and 5 are 5 and 10).

So the number of zeros mantissa of n factorial is a multiple of 2 and 5, and there are more multiples of 2 than there are multiples of 5, so you end up with as many zeros mantissa as there are multiples of 5.

The problem solving code

var trailingZeroes = function (n) {
  let res = 0;
  while (n >= 5) {
    let k = Math.floor(n / 5);
    res += k;
    n = k;
  }
  return res;
};
Copy the code

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

[LeetCode367 problem effective completely square number] | punch brush

[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush

[LeetCode160 topic cross linked list] | punch brush

[LeetCode1438 topic absolute difference does not exceed the limit of the longest continuous subarray] | punch brush

[LeetCode434 problem the number of words in a string] | punch brush

[LeetCode75 topic classification of color] | punch brush

[LeetCode513 problem to find the value of the trees left] | punch brush

[LeetCode94 title sequence in the binary tree traversal] | punch brush

[LeetCode617 topic merger binary tree] | punch brush

[LeetCode331 problem to verify the preamble of binary tree serialization] | punch brush

[LeetCode1281 integer of the product and the difference between the] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign