Problem

Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Example 1:

1
2
3
4
Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

1
2
3
4
Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:

1
2
3
Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 10^4

Follow up: Could you write a solution that works in logarithmic time complexity?

Solve

這題先搞懂 trailing zeroes，是指尾巴的0

要計算尾巴有幾個0很簡單就是算其中乘了幾次(5*2)

由於每次乘到5前，一定有2，所以找5有幾個就好

法1

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def trailingZeroes(self, n: int) -> int:
        output = 0

        for i in range(1, n + 1):
            while i % 5 == 0:
                output += 1
                i //= 5

        return output

Time Complexity : O(n)

當然這題不需要這麼麻煩

法2 用數學的方式

其實這題數學的思考方法沒這麼麻煩，直接計算幾個5就好

只需要注意當超過5的指數項，會增多

所以也不用O(n)

ex:

n = 10 2個5

n = 25 6個5

1
2
3
4
5
6
7
class Solution:
    def trailingZeroes(self, n: int) -> int:
        output = 0
        while n>=5:
            output += n//5
            n = n//5
        return output