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

Topic describes

This is 172 on LeetCode. Zero after factorial, medium difficulty.

Tag: math

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

Tip n! ∗ ∗ = n (n – 1) (n – 2) ∗… ∗ ∗ ∗ 1 2 3 n! = n * (n – 1) * (n – 2) * … * 3 * 2 * 1n! ∗ ∗ = n (n – 1) (n – 2) ∗… ∗ ∗ ∗ 1 2 3

Example 1:

Input: n = 3 Output: 0 Explanation: 3! = 6, not including trailing 0Copy the code

Example 2:

Input: n = 5 Output: 1 Explanation: 5! Theta is equal to 120, with a trailing 0Copy the code

Example 3:

Input: n = 0 Output: 0Copy the code

Tip:


  • 0 < = n < = 1 0 4 0 <= n <= 10^4

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

mathematics

For any n factorial n! n! In particular, the number of trailing zeros depends on the number of 101010 in the expansion, which can be derived from 2∗52 * 52∗5, so n! n! n! The trailing zero number of is the smaller value in the number of 222 and the number of 555 after the decomposition of the prime factors in the expansion formula.

That is, the problem is transformed into the number of 222 and 555 that can be decomposed by the prime factors of [1,n][1, n][1,n].

In order to be more general, we analyze the number of prime factors PPP decomposed for each number in [1,n][1, n]. According to the number of PPP that can be decomposed from each number, the following points are discussed:

  • The number of PPP in the range of [1,n][1, n][1,n] is c1=⌊np⌋c_1 = \left \lfloor \frac{n}{p} \right \ rfloorC1 =⌊ PN ⌋
  • Be able to factor out at least two PPPS as multiples of p2p^ 2P2, The number of such numbers in the range [1,n][1, n] is C2 =⌊np2⌋c_2 = \left \lfloor \frac{n}{p^2} \right \rfloorc2=⌊p2n⌋
  • .
  • Be able to factor out at least KKK PPPS as multiples of PKP ^ KPK, The number of such numbers in the range [1,n][1, n] is ck=⌊ NPK ⌋c_k = \left \lfloor \frac{n}{p^k} \right \rfloorck=⌊ PKN ⌋

Let’s define a legal one
k k Need to meet
p k ⩽ n p^k \leqslant n , each of the above numbers is a “subset” of the previous number (a number if
p k p^k Multiple of PI, it has to be PI
p k – 1 p^{k-1} A multiple of), so if a number is
p k p^k Is a multiple of, which appears in the number of sets is
k k And its ultimate contribution
p p The number of.

Back to the question, n! n! n! The number of prime factor 222 is:


∑ i = 1 k 1 ⌊ n 2 i ⌋ = ⌊ n 2 ⌋ + ⌊ n 2 2 ⌋ + . . . + ⌊ n 2 k 1 ⌋ \sum_{i = 1}^{k_1}\left \lfloor \frac{n}{2^i} \right \rfloor = \left \lfloor \frac{n}{2} \right \rfloor + \left \lfloor \frac{n}{2^2} \right \rfloor + … + \left \lfloor \frac{n}{2^{k_1}} \right \rfloor

n! n! n! The number of prime factor 555 is:


∑ i = 1 k 2 ⌊ n 5 i ⌋ = ⌊ n 5 ⌋ + ⌊ n 5 2 ⌋ + . . . + ⌊ n 5 k 2 ⌋ \sum_{i = 1}^{k_2}\left \lfloor \frac{n}{5^i} \right \rfloor = \left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^2} \right \rfloor + … + \left \lfloor \frac{n}{5^{k_2}} \right \rfloor

K2 ⩽k1k_2 \leqslant k_1k2⩽k1, At the same time, each item of the same iii satisfies ⌊n5i⌋⩽⌊n2i⌋\left \lfloor \frac{n}{5^ I} \right \rfloor \leqslant \left \lfloor \frac{n}{2^ I} \right 5 in ⌋ \ rfloor ⌊ ⩽ ⌊ 2 in ⌋, Know eventually ∑ I = 1, k2 ⌊ n5i ⌋ ⩽ ∑ I = 1 k1 ⌊ n2i ⌋ \ sum_ {I = 1} ^ {k_2} \ left \ lfloor \ frac {n} {5 ^ I} \ rfloor \ leqslant \ \ right sum_ {I = 1}^{k_1}\left \lfloor \frac{n}{2^ I}\ right \rfloor∑ I =1k2⌊5in⌋⩽∑ I =1k1⌊2in⌋, that is, the number of prime factors 555 must not exceed the number of prime factors 222. We just need to count the number of prime factors 555.

Code:

class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); }}Copy the code


class Solution:
    def trailingZeroes(self, n: int) - >int:
        return n // 5 + self.trailingZeroes(n // 5) if n else 0
Copy the code
  • Time complexity: O(log⁡n)O(\log{n})O(logn)
  • Space complexity: O(1)O(1)O(1), ignoring the extra space overhead caused by recursion

The last

This is the No.172 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks, so we will finish all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.