Factorial Trailing Zeroes - Leetcode Solution

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

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

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

Solution: The number of trailing zeroes in a number can be found by finding the number of factors of 10 in its prime factorization. Since 10 can be expressed as 2 x 5, we need to count the number of 2s and 5s in n! and take the minimum of the two since the number of 5s is always less than the number of 2s.

We can count the number of factors of 5 in n! by dividing n by 5 and then by 25 and so on until the quotient becomes less than 1. For example, in n = 25, we have one factor of 5 from 5 and one more factor of 5 from 25. Therefore, the number of factors of 5 in 25! is 6 (5, 10, 15, 20, 25, and an additional factor of 5 from 25).

Similarly, we can count the number of factors of 2 by dividing n by 2, 4, 8, and so on until the quotient becomes less than 1. However, since the number of factors of 2 is more than the number of factors of 5, we can just count the number of factors of 5 to find the number of trailing zeroes.

Code: class Solution { public: int trailingZeroes(int n) { int count = 0; while (n >= 5) { count += n / 5; n /= 5; } return count; } };

Time Complexity: The time complexity of this solution is O(log n) since we divide n by 5 repeatedly until the quotient becomes less than 1.

Space Complexity: The space complexity of this solution is O(1) since we only need a constant amount of space to store the count.

1