Factorial Trailing Zeros

Problem

Given a positive integer. Find the number of trailing zeros in the integer's factorial. For example the factorial of 10 is 3628800 so the algorithm should print 2

Solution

Let us start by a simple example. Factorial of 5 = 5 x 4 x 3 x 2 = 5 x 2 x 2 x 3 x 2 = 10 x 12 = 120. As you can see each pair of 5 x 2 contributes one zero in the final result. The problem reduces to finding the number of 5 x 2 pairs. Please refer to the code below for more details.

Code

Here is the code in C++

//Includes
#include <iostream>

//STD
using namespace std;

//Receives integer number as input
int TrailingZeros(int n)
{
	//Number of times 5 is a factor
	int fc = 0;

	//Number of times 2 is a factor
	int tc = 0;

	//A factorial is computed as the multiplication
	//of the number with all numbers before it so
	//we need to examine all of them
	for (int i = 1; i <= n; i++)
	{
		int num = i;

		//As long as the number can be
		//divided by 5 keep incrementing
		//the 5 counter
		while (num%5 == 0)
		{
			num = num/5;
			fc++;
		}

		//Once the number can no longer be divided
		//by 5 start checking if it can be divided
		//by 2 then keep incrementing the 2 counter
		while (num%2 == 0)
		{
			num = num/2;
			tc++;
		}
	}

	//Once the above loop is finished then we
	//have already determined the 5 and 2 factors
	//of the factorial. Each multiplication of 5 x 2
	//contributes one trailing zero in the final result
	if (tc == fc || tc < fc)
	{
		return tc;
	}
	else
	{
		return fc;
	}
}

//Main function
void main()
{
	//Print number of factorial trailing
	//zeros for numbers between 1 and 20
	for (int i = 0; i <= 20; i++)
	{
		cout << i << " : " << TrailingZeros(i) << endl;
	}
}

Leave a Reply