Factorial Trailing Zeroes

Updated on 23 May, 2025
Factorial Trailing Zeroes header image

Problem Statement

The problem requires us to determine how many trailing zeroes are present in the factorial of a given non-negative integer n. The factorial of a number n, denoted as n!, is the product of all positive integers less than or equal to n. This task specifically deals with finding zeroes that occur at the end of the factorial result.

Examples

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

Constraints

  • 0 <= n <= 104

Approach and Intuition

To solve this problem efficiently, understanding the formation of trailing zeros in a factorial is crucial. Trailing zeros are created by factors of 10 in the number, which is a product of 2 and 5. In the context of factorials, every even number contributes a factor of 2, and thus, there are usually more factors of 2 than factors of 5. This means the number of times 5 is present in the factors of numbers from 1 to n largely determines the count of trailing zeros.

Here's a step-by-step approach to find the number of trailing zeroes in n!:

  1. Initialize a count to zero. This will be used to tally the number of trailing zeroes.
  2. While n is greater than zero, perform the following:
    • Divide n by 5 and add the integer quotient to the count. This division is looking at how many multiples of 5, 25, 125, etc., are there up to n, as each contributes one or more factors of 5.
    • Set n to n divided by 5. This step prepares the next iteration to count the next power of 5.
  3. The count after exiting the loop gives the total number of trailing zeroes in n!.

This method is grounded in:

  • Counting contributions of factors of 5 - since 5s are the limiting factor (there are plenty of 2s due to even numbers),
  • Looking into higher powers of 5, like 25, 125, etc. - each multiple of these adds more than one 5 to the prime factorization of the number. For example, 25 adds two 5s.

This approach efficiently computes the result in logarithmic time relative to n, considering only factors related to 5.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    int countTrailingZeros(int x) {
        int count = 0;
        while (x > 0) {
            x /= 5;
            count += x;
        }
        return count;
    }
};

The solution provided addresses the problem of counting the number of trailing zeros in the factorial of a given number. The approach utilized in the C++ implementation leverages the observation that trailing zeros are formed by factors of 10, which is the product of 2 and 5. However, in factorials, 2s are more frequent than 5s, so the task reduces to counting the number of 5s in the factors of all numbers up to x.

  • The function countTrailingZeros is defined to compute this. It starts with a counter set to zero.
  • A while loop executes as long as x is greater than zero. Inside the loop, x is divided by 5, and the result, which represents the count of multiples of 5, is added to the counter.
  • This process effectively counts the total number of times 5 is a factor in all the numbers from 1 up to x.
  • Once the loop completes, the function returns the accumulated count, which corresponds to the number of trailing zeros in x! (x factorial).

This method is efficient, focusing specifically on counting the factors of 5, which are crucial for determining the number of trailing zeros in factorials. This ensures the solution is optimal and operates within a time complexity that is logarithmic relative to the input size, specifically O(log_5(x)).

java
class Solution {
    public int countTrailingZeros(int n) {
        int count = 0;
        long divisor = 5;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
}

The solution addresses the problem of determining the number of trailing zeroes in the factorial of a given integer n. The provided Java code efficiently computes this by counting the number of factors of 5 in the numbers from 1 to n. This is based on the fact that trailing zeros are created through the multiplication of the pair of prime factors 2 and 5, where the factor 2 is more abundant than 5.

Here's an outline of how the solution works:

  • Initialize a counter count to zero to track the number of trailing zeros.
  • Use divisor starting at 5, which helps in identifying numbers that are multiples of 5.
  • Loop until n is greater than 0:
    • Divide n by 5 to reduce the problem size and count the multiple of 5 factors at each stage.
    • Increment the count with the quotient of this division.
  • Return the total count as the number of trailing zeroes.

This approach limits unnecessary computations and makes the problem solvable in logarithmic time relative to n. Thus, the key to solving the problem lies in counting the multiples of 5 up to n.

c
int countTrailingZeros(int x) {
    int count = 0;
    while (x > 0) {
        x /= 5;
        count += x;
    }
    return count;
}

The provided C code calculates the number of trailing zeros in the factorial of a given integer x. The key concept exploited here revolves around the fact that trailing zeros are produced by multiplying the factors 2 and 5, however, since factorials contain more factors of 2 than 5, the number of trailing zeros is determined by the number of times 5 is a factor in the numbers from 1 to x.

Here's an outline of how the code operates:

  • Initialize a counter variable count to zero.
  • Use a while loop to execute as long as x is greater than zero.
  • Inside the loop:
    • Divide x by 5 and assign it back to x.
    • Increment count by the value of x after division.
  • The loop iterates, reducing the value of x each time by a factor of 5, adding up all values that indicate how many factors of 5 are present in each cycle.
  • Once x is reduced to zero, the loop exits, and the function returns the count, which represents the number of trailing zeros in x factorial.

By applying this method, you leverage an efficient way to calculate trailing zeros without needing to compute the factorial explicitly, thus maintaining efficiency even for large inputs.

js
var countTrailingZeros = function (number) {
    let count = 0;
    while (number > 0) {
        number = Math.floor(number / 5);
        count += number;
    }
    return count;
};

The solution provided computes the number of trailing zeros in the factorial of a specified number using JavaScript. The code defines a function countTrailingZeros which takes number as an argument. The calculation is based on how many times the number can be divided by 5, as each division essentially counts the number of 5s in the factors, which pair with the 2s to form a trailing zero.

Here's a breakdown of the operation:

  • Initialize a counter count to zero to store the number of times the number can be completely divided by 5.
  • Utilize a while loop that runs as long as number is greater than zero.
  • Inside the loop, divide the number by 5 using Math.floor to get integer division and update number.
  • Accumulate the result of the division into count after each division.
  • At the end of the loop when the number can no longer be divided by 5, the function returns count, which represents the number of trailing zeros in the factorial of the initial number.

This method efficiently counts trailing zeros without calculating the factorial explicitly, thereby preventing potential overflow and excessive computational resource usage for large numbers.

python
class Solution:
    def countTrailingZeros(self, value: int) -> int:
        count = 0
        while value > 0:
            value //= 5
            count += value
        return count

The problem, Factorial Trailing Zeroes, focuses on finding the number of trailing zeroes in the factorial of a given number. The Python implementation provided defines a class Solution with a method countTrailingZeros that efficiently calculates this by continuously dividing the input value by 5 and adding the quotient to a cumulative count until the value is zero.

Here’s a concise breakdown:

  • The function takes an integer value which represents the number to calculate the factorial trailing zeros for.
  • Initialize count to 0. This will store the number of trailing zeroes.
  • Use a while loop that runs as long as value is greater than 0.
  • Inside the loop, perform integer division of value by 5 and assign the result back to value. This step reduces the number by a factor of 5 in each iteration.
  • Add the new value to count after each division to tally the number of times factors of 5 can be counted in the factorial, which correlates directly to the number of trailing zeros.
  • Once the loop concludes, return the count as it represents the total number of trailing zeroes.

Utilize this approach to get the number of trailing zeros for factorial of any non-negative integer efficiently, making the solution particularly useful for large numbers.

Comments

No comments yet.