Problem Statement
Count the number of trailing zeroes in the factorial of a given number.
Example
-
Input: trailingZeroes(5)
Output: 1
Explanation: ( 5! = 120 ), which has 1 trailing zero.
-
Input: trailingZeroes(10)
Output: 2
Explanation: ( 10! = 3,628,800 ), which has 2 trailing zeroes.
-
Input: trailingZeroes(25)
Output: 6
Explanation: ( 25! = 15,511,210,043,330,985,984,000 ), which has 6 trailing zeroes.
Brute Force Approach
Approach
Idea: Calculate the factorial of the number, then count the number of trailing zeroes by repeatedly dividing the factorial by 10.
Steps
- Calculate the factorial of the number using an iterative loop.
- Divide the factorial by
10 repeatedly, counting how many times it can be divided without leaving a remainder.
- Return the count.
Time & Space Complexity
- Time Complexity: O(n + d), where
n is the input number, and d is the number of digits in the factorial.
- Computing the factorial is O(n), and counting trailing zeroes is O(d).
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: n = 5
- Calculate 5! = 1 2 3 4 5 = 120.
- Count trailing zeroes:
- 120 % 10 = 0: Increment count to 1, divide 120 / 10 = 12.
- 12 % 10 != 0: Stop counting.
- Return 1.
Efficient Approach Using Factorial Prime Factors
Approach
Idea: Trailing zeroes in a factorial are caused by factors of 10, which are formed by multiplying 2 and 5. Since there are always more factors of 2 than 5, the number of trailing zeroes is determined by the number of factors of 5 in the factorial.
Steps
- Initialize a counter to
0.
- Divide the number by
5 repeatedly, adding the result of each division to the counter.
- Stop when the division result becomes
0.
- Return the counter.
Time & Space Complexity
- Time Complexity: O(log₅(n))
- The loop runs approximately
log₅(n) iterations.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet