LeetCode 0172. Factorial Trailing Zeroes Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

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?

Solutions

Solution 1: Mathematics

The problem is actually asking how many factors of 5 are there in [1,n].

Let's take 130 as an example for analysis:

1. Divide by 5 for the first time, get 26, indicating that there are 26 numbers containing the factor 5;
2. Divide by 5 for the second time, get 5, indicating that there are 5 numbers containing the factor 5^2;
3. Divide by 5 for the third time, get 1, indicating that there is 1 number containing the factor 5^3;
4. Sum up to get the count of all factors of 5 in [1,n].

The time complexity is O(log n), and the space complexity is O(1).

PythonJavaC++GoTypeScript

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

class Solution { public int trailingZeroes(int n) { int ans = 0; while (n > 0) { n /= 5; ans += n; } return ans; } }(code-box)

class Solution { public: int trailingZeroes(int n) { int ans = 0; while (n) { n /= 5; ans += n; } return ans; } };(code-box)

func trailingZeroes(n int) int { ans := 0 for n > 0 { n /= 5 ans += n } return ans }(code-box)

function trailingZeroes(n: number): number { let ans = 0; while (n > 0) { n = Math.floor(n / 5); ans += n; } return ans; }(code-box)