Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an integer n, return the number of trailing zeroes in n! Could you write a solution that works in logarithmic time complexity?
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
Bruteforce Algorithm to Compute the Trailing Zeros for Factorial
First compute the actual factorial value, then count the number of zeros:
1 2 3 4 5 6 7 8 9 10 11 | def trailingZeroes(n: int) -> int: # Calculate n! n_factorial = 1 for i in range(2, n + 1): n_factorial *= i # Count how many 0's are on the end. zero_count = 0 while n_factorial % 10 == 0: zero_count += 1 n_factorial //= 10 return zero_count |
def trailingZeroes(n: int) -> int: # Calculate n! n_factorial = 1 for i in range(2, n + 1): n_factorial *= i # Count how many 0's are on the end. zero_count = 0 while n_factorial % 10 == 0: zero_count += 1 n_factorial //= 10 return zero_count
Time complexity O(N^2) as we can’t treat multiplication O(1) as the value grows exponentially. Also it takes significant space to store the result of factorial N!.
Count the number of Factor 5
If we think about it, the number of zeros are made by a pair of 5 and 2. And the number of 2s is far more than the number of 5s. Therefore, the number of trailing zeros is determined by the number of factor 5.
We can count it this way:
1 2 3 4 5 6 7 8 | def trailingZeroes(n: int) -> int: zero_count = 0 for i in range(5, n + 1, 5): current = i while current % 5 == 0: zero_count += 1 current //= 5 return zero_count |
def trailingZeroes(n: int) -> int: zero_count = 0 for i in range(5, n + 1, 5): current = i while current % 5 == 0: zero_count += 1 current //= 5 return zero_count
Alternatively, we keep tracking a multiple of 5.
1 2 3 4 5 6 7 8 | def trailingZeroes(n: int) -> int: zero_count = 0 for i in range(5, n + 1, 5): power_of_5 = 5 while i % power_of_5 == 0: zero_count += 1 power_of_5 *= 5 return zero_count |
def trailingZeroes(n: int) -> int: zero_count = 0 for i in range(5, n + 1, 5): power_of_5 = 5 while i % power_of_5 == 0: zero_count += 1 power_of_5 *= 5 return zero_count
The complexity is O(N). As the inner loop tends to amortizes to O(1). The most numbers contain a single factor of 5.
Count the number of Factor 5 Efficiently
The number of zeros for factorial N! is determined by number of 5’s and we can accumulate the 5’s in 25, 125, 625 .. as well.. Thus, the total number of 5’s can be computed via:
1 2 3 4 5 6 7 | def trailingZeroes(n: int) -> int: zero_count = 0 current_multiple = 5 while n >= current_multiple: zero_count += n // current_multiple current_multiple *= 5 return zero_count |
def trailingZeroes(n: int) -> int: zero_count = 0 current_multiple = 5 while n >= current_multiple: zero_count += n // current_multiple current_multiple *= 5 return zero_count
Alternatively, we can divide and count:
1 2 3 4 5 6 | def trailingZeroes(n: int) -> int: zero_count = 0 while n > 0: n //= 5 zero_count += n return zero_count |
def trailingZeroes(n: int) -> int: zero_count = 0 while n > 0: n //= 5 zero_count += n return zero_count
The time complexity is O(LogN).
See also: C/C++ Coding Exercise – Factorial Trailing Zeroes
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Finding Pythagorean Triplets in Array using Two Pointer or Hash Set
Next Post: Algorithms to Union Two Sorted Linked Lists