Trailing Zeroes Editorial

Practice Problem Link: Trailing Zeroes | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a number ‘n’, find the no of trailing zeroes in the factorial of ‘n’.

Naive Approach

In the naive approach, we can calculate the factorial of n, and then naively calculate the number of trailing zeroes in it using a while loop.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int trailingZeroesInFactorial(int n) {
   int count = 0;
   int factorial = 1;
   for (int i = 1; i <= n; i++) {
       factorial *= i;
   }
   while (factorial % 10 == 0) {
       count++;
       factorial /= 10;
   }
   return count;
}

Java

class Solution {
   int trailingZeroesInFactorial(int n) {
       int count = 0;
       int factorial = 1;
       for (int i = 1; i <= n; i++) {
           factorial *= i;
       }
       while (factorial % 10 == 0) {
           count++;
           factorial /= 10;
       }
       return count;
   }
}

Optimal Approach

We will try to solve this problem in logarithmic time complexity.

Observe that we basically want to find the number of 10s in the factors of n!. Since 10 = 2 * 5, we basically need the minimum of the number of 2s and the number of 5s in the factorial of the number, so that we can pair up all the 2s and 5s to form 10s.

It can be proved that the number of 2s in n! is always greater than or equal to the number of 5s in n!. So, our problem boils down to find the number of 5s in the prime factors of n!.

This can be solved by using the following formula: Answer = floor(n / 5) + floor(n / 25) + …. till the sequence converges to zero.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int trailingZeroesInFactorial(int n) {
   int count = 0;
   int powerOf5 = 5;
   while(n >= powerOf5) {
       count += (n / powerOf5);
       powerOf5 *= 5;
   }
   return count;
}

Java

class Solution {
   int trailingZeroesInFactorial(int n) {
       int count = 0;
       int powerOf5 = 5;
       while(n >= powerOf5) {
           count += (n / powerOf5);
           powerOf5 *= 5;
       }
       return count;
   }
}