172-factorial-trailing-zeroes

Try it on leetcode

Description

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:

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

Example 2:

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

Example 3:

Input: n = 0
Output: 0

 

Constraints:

• 0 <= n <= 104

 

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

Solution(Python)

class Solution:
    def trailingZeroes(self, n: int) -> int:
        return self.math(n)

    # Time Complexity1: O(n)
    # space Complexity: O(1)
    # overflow error for n > 20
    def bruteforce(self, n):
        # generate factorial of number
        fact = 1
        for i in range(2, n + 1):
            fact *= i
        # calculate trailing zeros
        cnt = 0
        rem = 0
        while fact >= 0 and rem == 0:
            rem = fact % 10
            fact = fact // 10
            if rem == 0:
                cnt += 1
        return cnt

    # prime factor of 10 = 2 aND 5
    # even numbers has 2 and onlyconsider 5
    # trailing zeros = n/5 + n/25 + n/125
    # Time Complexity: O(log_5_n )
    def math(self, n):
        if n <= 0:
            return 0

        cnt = 0

        while n >= 5:
            n //= 5
            cnt += n
        return cnt