Teaching Kids Programming – Compute the Number of Trailing Zeros for Factorial N


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:

tex_2e1e507e935f89391fb573f249c3cc4d Teaching Kids Programming - Compute the Number of Trailing Zeros for Factorial N algorithms math python teaching kids programming youtube video

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) —

GD Star Rating
loading...
615 words
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

The Permanent URL is: Teaching Kids Programming – Compute the Number of Trailing Zeros for Factorial N

Leave a Reply