Trailing Zeros in Factorial

Problem Statement

Given an integer n, our task is to write a function that returns the count of trailing zeros in n!. Here n! is the factorial of a number n which is the product of all numbers in the range $[1, n]$.

Example :

Input: n = 3
Output: 0

Input: n = 5
Output: 1

Input: n = 20
Output: 4

Explanation

Example – 1 :
When $n = 3$, Factorial of 3 is 6, which has no trailing zeros in factorial.

Example – 2 :
When $n = 5$, Factorial of 5 is 120, which has no trailing zeros in factorial.

Example – 3 :
When $n = 20$, Factorial of 20 is 2432902008176640000, which has four trailing zeros in factorial.

Constraints

$0 <= n <= 10^{4}$

Approach – 1 : Naive Approach

Algorithm :

In this approach, the intuition is to calculate the value of n! and then count the number of trailing zeros in factorial. The number of zeros can be measured by repeatedly dividing the value of the factorial by 10 until the last digit becomes non-zero.

Implementation

Implementation of Naive Approach in C++ :

#include <iostream>
using namespace std;

int trailingZeros(int n) {

    int fact = 1;
    // calculating factorial
    for (int i = 1; i <= n; i++) {
        fact = fact * i;
    }

    int zeros = 0;
    // counting the number of trailing zeros
    while (fact % 10 == 0) {
        zeros++;
        fact = fact / 10;
    }

    return zeros;
    }

int main() {
    cout << trailingZeros(6);
    return 0;
}

Output :

1

Implementation of Naive Approach in Java :

import java.io.*;

public class Main {

  public static int trailingZeros(int n) {
    int fact = 1;
    // calculating factorial
    for (int i = 1; i <= n; i++) {
      fact = fact * i;
    }

    int zeros = 0;
    // counting the number of trailing zeros
    while (fact % 10 == 0) {
      zeros++;
      fact = fact / 10;
    }

    return zeros;
  }

  public static void main(String[] args) {
    System.out.println(trailingZeros(6));
  }
}

Output :

1

Implementation of Naive Approach in Python :

def trailingZeros(n):
    fact = 1
    zeros = 0

    # calculating factorial
    for i in range(1, n + 1):
        fact = fact * i

    # counting the number of trailing zeros
    while (fact % 10) == 0:
        fact = fact // 10
        zeros += 1

    return zeros

print(trailingZeros(20))

Output :

4

Complexity Analysis

Time Complexity :

• Since we are iterating over n times to calculate the factorial value, the Time Complexity for calculating the number of trailing zeros in factorial is $O(n)$.

Space Complexity :

• While no auxiliary space is required to calculate the number of trailing zeros in factorial, Space Complexity is $O(1)$.

Approach – 2 : Optimal Approach

Algorithm :

The above approach can lead to an overflow in case of bigger numbers as factorial could be a really big number. So, the intuition for a better approach is to consider that a trailing zero is produced when a number is multiplied by 10. The prime factors of 10 are 2 and 5.

So, our task now becomes to just count the number of 2s and 5s.

Let us consider an example, where n = 5 :

5! = 2 x 2 x 2 x 3 x 5

The number of trailing zeros in the factorial of 5 will be 1 because only one pair of 2 and 5 can be made from one 5 and three 2s in the prime factors of 5!.

In the above example, we can see that the number of 2s in prime factors is always more than or equal to the number of 5s.

So if we count the number of 5s in the prime factors, our task is done. But how to calculate the number of 5s in prime factors of n!? An easy method of doing this would be using Legendre’s Formula, which is used to get the highest power of a prime number p in n!.

Here, $V_p(n!)$ represents the highest power in p, in a way that $p^n$ divides n! where p is a prime number.

$[n]$ is the greatest integer function. $[4.99] = 4, [4.01] = 4, [-3.01] = 4$

The above formula will compute the exact number of 5s in n! as it will consider all multiples of 5 that are less than n. This will also consider all higher power multiples of 5 i.e 25, 125, etc.

Therefore, the formula gets transformed to the following for calculating trailing zeros in factorial of a number n :

Where k = floor of $log_5n$.

Let us now solve a few examples using this formula :

Example – 1 :
number of trailing zeros in 24! will be
$[24/5] = [4.8] = 4$ trailing zeros

Example – 2 :
number of trailing zeros in 123! will be :
$[123/5] = [24.6] = 24$ trailing zeros.
$[123/25] = [4.92] = 4$ trailing zeros.

Therefore, 123! has a total of 28 trailing zeros

The final algorithm is :

• Create a function trailing_zeros(int number) that takes an integer n and returns the count of trailing zeros in factorial of n.
• Check for the edge case where, if n < 0, return -1.
• Initialize count = 0.
• Traverse using a for loop and divide the number n by powers of 5 at every iteration.
• If number/i is greater than or equal to 1, add number/i to count.
• At the end of for loop, the return count as result.

Implementation

Implementation of Optimal Approach in C++ :

#include <iostream>
using namespace std;

int trailingZeros(int n) {
    // in case of negative numbers
    if (n < 0)
        return -1;

    // initializing count variable
    int count = 0;

    // dividing n by powers of 5 and updating count
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;

    return count;
    }

int main() {
    int n = 100;
    cout << "Count of trailing 0s in " << 100 << "! is "<< trailingZeros(n);
    return 0;
}

Output :

The count of trailing 0s in 100! is 24

Implementation of Optimal Approach in Java :

import java.io.*;

class Main {

  static int trailingZeros(int n) {
    // in case of negative numbers
    if (n < 0) return -1;

    // initializing count variable
    int count = 0;

    // dividing n by powers of 5 and updating count
    for (int i = 5; n / i >= 1; i *= 5) count += n / i;

    return count;
  }

  public static void main(String[] args) {
    int n = 100;
    System.out.println(
      "Count of trailing 0s in " + n + "! is " + trailingZeros(n)
    );
  }
}

Output :

The count of trailing 0s in 100! is 24

Implementation of Optimal Approach in Python :

def trailingZeros(n):
# in case of negative numbers
    if(n < 0):
        return -1

    # initializing count variable
    count = 0

    # dividing n by powers of 5 and updating count
    while(n >= 5):
        n //= 5
        count += n

    return count

n = 100
print("Count of trailing 0s in 100! is", trailingZeros(n))

Output :

The count of trailing 0s in 100! is 24

Complexity Analysis

Time Complexity :

• In this approach, n is divided by 5 till it becomes 0. Therefore, the number of iterations till which the program will execute is equal to $floor(log_5n)$, which makes the Time Complexity as $O(log_5n)$.
• Space Complexity :
• Similar to the previous approach no auxiliary space is required to calculate the number of trailing zeros in factorial, Space Complexity is $O(1)$.
  

Conclusion

• The drawback of using the naive approach is that it calculates the factorial of given n before computing the result, whose value can grow very large and can cause an overflow issue.
• The optimal approach uses Legendre’s Formula to compute the highest power of any prime number p in n!, which in this problem calculates the highest power of 5 in n!.
• The time and Space Complexity of the Optimal Approach to calculate the number of trailing zeros in factorial is $O(log_5n)$ and $O(1)$ respectively.