動機

這應該可以用5進位制來看，但要先把數論找回來

Problem

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

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: n = 0Output: 0

 

Constraints:

  • 0 <= n <= 104

Sol Ver1

找10的因數

def f(val,n):
    ret = 0
    while val % n == 0:
        val = val // n
        ret += 1
    return ret
class Solution:
    def trailingZeroes(self, n: int) -> int:
        two = 0
        five = 0
        for k in range(1,n+1):
            two += f(k,2)
            five += f(k,5)
        return min(two,five)

Sol Ver2

2一定比5多

def f(val,n):
    ret = 0
    while val % n == 0:
        val = val // n
        ret += 1
    return ret
class Solution:
    def trailingZeroes(self, n: int) -> int:
        two = 0
        five = 0
        for k in range(1,n+1):
            #two += f(k,2)
            five += f(k,5)
        return five #min(two,five)

Sol Ver3

把數字列出來，會看到每5個就會有5 所以就一直除5把商都加起來

1 2 3 4 5
6 7 8 9 (2*5)
11 12 13 14 (3*5)
...
21 22 23 24 (5*5)

25 // 5 = 5
5 // 5 = 1

class Solution:
    def trailingZeroes(self, n: int) -> int:
        five = 0
        while n >= 5:
            five += n // 5
            n = n // 5
            
        return five