Jobs

Interviews

Discussions

Factorial Trailing Zeroes

Medium

Google

2 views

Topics:

Bit ManipulationGreedy Algorithms

Given an integer n, return the number of trailing zeroes in n!. Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

For example:

If n = 3, the output should be 0. Explanation: 3! = 6, which has no trailing zeros.
If n = 5, the output should be 1. Explanation: 5! = 120, which has one trailing zero.
If n = 0, the output should be 0.

Write an algorithm with the best possible time complexity. What are the edge cases to consider?

Factorial Trailing Zeroes

Medium

Google

2 views

Topics:

Bit ManipulationGreedy Algorithms

Given an integer n, return the number of trailing zeroes in n!. Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

For example:

If n = 3, the output should be 0. Explanation: 3! = 6, which has no trailing zeros.
If n = 5, the output should be 1. Explanation: 5! = 120, which has one trailing zero.
If n = 0, the output should be 0.

Write an algorithm with the best possible time complexity. What are the edge cases to consider?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input integer n? Is there a maximum value?
Can the input integer n be negative or zero?
Should I consider any specific constraints related to integer overflow when calculating factorials?
Is the expectation to return an integer representing the count of trailing zeroes?
Is there any need to optimize for extremely large values of n, assuming standard integer data types are used?

Brute Force Solution

Approach

The problem asks us to figure out how many trailing zeros are at the end of the factorial of a number. A brute force approach directly calculates the factorial and then counts the trailing zeros by repeatedly dividing by ten.

Here's how the algorithm would work step-by-step:

First, calculate the factorial of the given number. This means multiplying all whole numbers from 1 up to that number together.
Now, look at the result of that factorial. Count how many zeros are at the very end of the number.
To do this, keep dividing the factorial result by 10 until you can't divide it evenly anymore (i.e., there's a remainder).
Each time you successfully divide by 10, increase your zero count by one.
The final zero count is the answer: how many trailing zeros are in the factorial.

Code Implementation

def factorial_trailing_zeroes_brute_force(number):
    factorial_result = 1

    # Calculate the factorial of the given number.
    for current_number in range(1, number + 1):
        factorial_result *= current_number

    trailing_zero_count = 0

    # Count the trailing zeros by repeatedly dividing by 10.
    while factorial_result > 0:
        if factorial_result % 10 == 0:

            factorial_result //= 10
            trailing_zero_count += 1

            # This is the core logic to identify and count trailing zeros

        else:
            break

    return trailing_zero_count

Big(O) Analysis

Time Complexity

O(n!) – The first step calculates the factorial of the input number n. This involves multiplying all numbers from 1 to n, requiring n-1 multiplication operations. Calculating the factorial itself takes O(n) multiplications, but the size of the factorial grows extremely rapidly (n!). The second step counts trailing zeros by repeatedly dividing the calculated factorial by 10. This division process depends on the magnitude of the factorial, meaning it will perform the division on average n! times. Therefore the overall time complexity is dominated by the factorial calculation and the subsequent divisions based on that factorial's size leading to O(n!).

Space Complexity

O(1) – The provided plain English explanation calculates the factorial directly. It then repeatedly divides the factorial result by 10. This approach doesn't use any auxiliary data structures whose size scales with the input number N. The algorithm only stores the input number N, the calculated factorial, and a zero counter, all of which take up constant space regardless of the input size. Therefore, the space complexity is constant.

Optimal Solution

Approach

The key is to realize trailing zeroes in factorials come from factors of 5. Instead of calculating the factorial, we directly count how many times 5 appears as a factor in the numbers leading up to the given number. This is much faster than calculating the factorial and then counting zeroes.

Here's how the algorithm would work step-by-step:

Recognize that trailing zeroes are created by pairs of 2 and 5 in the prime factorization of the factorial.
Realize that there will always be more factors of 2 than 5, so we only need to count the factors of 5.
Divide the input number by 5 to find how many numbers between 1 and the input number are divisible by 5. This tells us how many multiples of 5 contribute a factor of 5.
Divide the input number by 25 (5 squared) to count the numbers that contribute an additional factor of 5 (e.g., 25, 50, 75).
Continue dividing the input number by increasing powers of 5 (125, 625, etc.) until the result of the division is zero.
Add up all the results from these divisions. This sum is the total number of factors of 5, and therefore the number of trailing zeroes.

Code Implementation

def factorial_trailing_zeroes(number):
    trailing_zeroes_count = 0
    power_of_five = 5

    # Count multiples of 5, 25, 125, etc.
    while number // power_of_five > 0:
        # Accumulate count of factors of 5.
        trailing_zeroes_count += number // power_of_five

        power_of_five *= 5

    # Return the total count of trailing zeroes.
    return trailing_zeroes_count

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iteratively divides the input number n by increasing powers of 5. The number of iterations is determined by how many times n can be divided by 5 before reaching zero. This is effectively a logarithmic operation with a base of 5. Therefore, the time complexity is O(log n) where n is the input number.

Space Complexity

O(1) – The provided algorithm calculates the number of trailing zeroes in a factorial without using any auxiliary data structures that scale with the input number N. It only uses a few constant space variables to store intermediate results during the divisions by powers of 5 and the accumulating sum of these divisions. The space required does not depend on the size of the input N, meaning it remains constant regardless of how large N is. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Negative input n	Factorial is not defined for negative numbers, return 0 as there are no trailing zeroes.
Input n equals 0	0! is 1, which has no trailing zeroes, so return 0.
Input n equals 1	1! is 1, which has no trailing zeroes, so return 0.
Large input n, close to integer limit	Use long data type to prevent integer overflow during calculations with large n or optimize for time complexity using only division and counting factors of 5.
Input n is a multiple of 5, 25, 125 (powers of 5)	The algorithm should correctly count multiple factors of 5 (e.g., 25 contributes two factors of 5).
Integer overflow when calculating factorial directly (if attempted naively)	Avoid calculating the factorial directly; instead, count the factors of 5.
Extremely large n that may cause performance degradation	Ensure the solution has logarithmic or constant time complexity related to the range, avoiding iterating through all numbers up to n.
Input close to max integer value	Be sure to prevent overflow when dividing to count the multiples of 5.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the input integer n? Is there a maximum value?
Can the input integer n be negative or zero?
Should I consider any specific constraints related to integer overflow when calculating factorials?
Is the expectation to return an integer representing the count of trailing zeroes?
Is there any need to optimize for extremely large values of n, assuming standard integer data types are used?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the factorial of the given number. This means multiplying all whole numbers from 1 up to that number together.
Now, look at the result of that factorial. Count how many zeros are at the very end of the number.
To do this, keep dividing the factorial result by 10 until you can't divide it evenly anymore (i.e., there's a remainder).
Each time you successfully divide by 10, increase your zero count by one.
The final zero count is the answer: how many trailing zeros are in the factorial.

Code Implementation

def factorial_trailing_zeroes_brute_force(number):
    factorial_result = 1

    # Calculate the factorial of the given number.
    for current_number in range(1, number + 1):
        factorial_result *= current_number

    trailing_zero_count = 0

    # Count the trailing zeros by repeatedly dividing by 10.
    while factorial_result > 0:
        if factorial_result % 10 == 0:

            factorial_result //= 10
            trailing_zero_count += 1

            # This is the core logic to identify and count trailing zeros

        else:
            break

    return trailing_zero_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Recognize that trailing zeroes are created by pairs of 2 and 5 in the prime factorization of the factorial.
Realize that there will always be more factors of 2 than 5, so we only need to count the factors of 5.
Divide the input number by 5 to find how many numbers between 1 and the input number are divisible by 5. This tells us how many multiples of 5 contribute a factor of 5.
Divide the input number by 25 (5 squared) to count the numbers that contribute an additional factor of 5 (e.g., 25, 50, 75).
Continue dividing the input number by increasing powers of 5 (125, 625, etc.) until the result of the division is zero.
Add up all the results from these divisions. This sum is the total number of factors of 5, and therefore the number of trailing zeroes.

Code Implementation

def factorial_trailing_zeroes(number):
    trailing_zeroes_count = 0
    power_of_five = 5

    # Count multiples of 5, 25, 125, etc.
    while number // power_of_five > 0:
        # Accumulate count of factors of 5.
        trailing_zeroes_count += number // power_of_five

        power_of_five *= 5

    # Return the total count of trailing zeroes.
    return trailing_zeroes_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Negative input n	Factorial is not defined for negative numbers, return 0 as there are no trailing zeroes.
Input n equals 0	0! is 1, which has no trailing zeroes, so return 0.
Input n equals 1	1! is 1, which has no trailing zeroes, so return 0.
Large input n, close to integer limit	Use long data type to prevent integer overflow during calculations with large n or optimize for time complexity using only division and counting factors of 5.
Input n is a multiple of 5, 25, 125 (powers of 5)	The algorithm should correctly count multiple factors of 5 (e.g., 25 contributes two factors of 5).
Integer overflow when calculating factorial directly (if attempted naively)	Avoid calculating the factorial directly; instead, count the factors of 5.
Extremely large n that may cause performance degradation	Ensure the solution has logarithmic or constant time complexity related to the range, avoiding iterating through all numbers up to n.
Input close to max integer value	Be sure to prevent overflow when dividing to count the multiples of 5.