topics@today: Trailing Zeroes in a Factorial!

Hey, 👲

you're probably here searching for the solution to an interestingly difficult task of counting the number of trailing 0's in the factorial of a number.

Straightaway, here's the solution:

f(n) = [n/5] + [n/52] + [n/53] + ... [<1]

[ where [ ] is the greatest integer function (also called box or floor function) that truncates the fractional part of a real number & returns an integer value. ]

> Examples:

i) for n = 23:

f(n) = f(23) = [23/5] + [23/52] = [4.6] + [0.92] = 4 + 0 = 4

Hence, 23! has 4 trailing 0s.

👉 Reason:

How many multiples of 5 are between 1 and 23?

We have: 5, 10, 15, and 20 - four multiples of 5 which paired with 2's from the even factors, makes for 4 factors of 10.

Thus, 23! has four trailing zeroes.

ii) Find the number of trailing zeroes in the expansion of 1000!

for n = 1000:

f(n) = f(1000) = [1000/5] + [1000/52] + [1000/53] + [1000/54] + [1000/55] = [200] + [40] + [8] + [1.6] + [0.32] = 200 + 40 + 8 + 1 = 249

Hence, 1000! has 249 trailing 0s.

👉 Reason:

There are 1000 ÷ 5 = 200 multiples of 5 between 1 and 1000.

The next power of 5 i.e. 25 has 1000 ÷ 25 = 40 multiples between 1 and 1000.

The next power of 5 i.e. 125 has 1000 ÷ 125 = 8 multiples between 1 and 1000.

The next power of 5 i.e. 625 fits in the expansion too, and has 1000 ÷ 625 = 1.6 multiples implying 1 complete multiple between 1 and 1000. (the remaining = 1000-625 accounts for that '0.6' excess which is hence truncated)

Thus, in total, we have 200 + 40 + 8 + 1 = 249 occurrences of the factor 5 in the expansion of 1000!

Solution approach:

a) Bruteforce: first calculate n!, then count trailing 0s in the result (by repeatedly dividing the factorial by 10 till the remainder is 0).

Disadvantage: Inefficient - overflow issues for larger integers as the factorial of a number is a big number. (factorial grows like a monster!)

b) Efficient way lies in the prime factors responsible for the trailing 0s : 2 and 5.

Counting frequencies of 5 is enough (since a 2 without a 5 can't make up a 10). Like there are two 5s and eight 2s in prime factors of 11! (2^8 * 3^4 * 5^2 * 7). So no. of trailing 0s = 2.

Program in C++:

/*
program in C++ to display
number of trailing zeroes in n!
*/
#include <iostream>
using namespace std;

// the required functionality:
int func(int n)
{
int ans = 0; // to store occurrences of 5

// dividing n by powers of 5:-
for (int i = 5; n/i >= 1; i *= 5)
ans += n/i; //update ans

return ans;
}

// driver Code:-
int main()
{
int n;
cout<<"Enter any number: ";
cin>>n;
printf("%d! has %d trailing zeroes!", n, func(n));

return 0;
}