Wednesday, August 12, 2015

Number of Trailing Zeroes of Factorial

Problem

Given a positive integer $N$, find the number of trailing zero $N!$ has.

For example, $5! = 120$ has $1$ trailing zero and $10! = 3628800$ has $2$.

Brute Force Solution

Brute Force solution for this problem involves calculating the value of $N!$, which is overkill in this situation. Read the section on Brute Force on this article before you continue - [1] Number of Digits of Factorial

The brute force solution for this problem faces same limitation as [1]. We cannot calculate $N!$ for $N > 20$ using long long variable and using Big Integer is too slow, $O(N^2)$, if we assume number of digits in $N!$ increase by $1$ in each step.

Solution Using Factorization

Suppose a there is a number $x$, with $y$ trailing zeroes at its end, then can't we write that number as $x = z \times 10^y$?

For example, $x = 12300$ and it has $2$ trailing zeroes. Then we can write $x = 123 \times 10^2$.

Therefore, for every factor of $10$, $x$ gets a trailing zero. If we can find out number of $10$ in $N!$ then we can easily count its number of trailing zeroes.

How do we form a $10$? We form a $10$ by multiplying $2$ and $5$. So we need to find out how many $2$ and $5$ $N!$ has. This can be found using the idea for factorizing $N!$. The idea is discussed in [2]Prime Factorization of Factorial. We will be using $\text{factorialPrimePower}()$ function from that post.

So all we need to do is call $x = \text{factorialPrimePower}(2)$ and $y = \text{factorialPrimePower}(5)$ to find out the frequency of those primes. For every pair of $(2,5)$ we get one $10$ factor. So how many pairs can we make if we have $x$ number of $2$'s and $y$ number of $5$'s? We can make $MIN(x,y)$ pairs.

For example, for $10!$ we have $x = \frac{10}{2} + \frac{10}{4} + \frac{10}{8}= 5 + 2 + 1 = 8$ and $y =  \frac{10}{5} = 2$. Therefore number of trailing zero is $MIN(x,y) = MIN(8,2) = 2$.

Trailing Zeroes in Different Base

We solved the problem for decimal base. Now what if we want to know how many trailing zero does $N!$ has if we convert $N!$ to base $B$?

For example, how many trailing zero does $10!$ has in base $16$? In order to solve this, we need to know how number system works. Read the post [3]Introduction to Number System to learn more.

Previously we said that for decimal numbers, multiplying them with $10$ increase their trailing zeroes. Can something similar be said for the base $16$? Yes. Look at the following values:

$(1)_{16} = 1 \times 16^0$
$(10)_{16} = 1 \times 16^1$
$(100)_{16} = 1 \times 16^2$

Everytime we multiply a number with its base, all its digits shift a place to left and at the end a $0$ is added. So for a number in base $B$, if we multiply it by $B$ it gets a trailing zero at its end. 

So all we need to do is find out how many $B$ does $N!$ has in it. For base $16$, we need to find out how many times $16 = 2^4$ occurs in $N!$. For that we find out how many times $2$ occurs using $x = \text{factorialPrimePower}(2)$ and since we get $16$ for each $2^4$, we conclude that $N!$ has $\frac{x}{4}$ trailing zeroes.

This is extended for any base. Factorize the base $B$ and find out occurances of each prime. Then figure out how many combinations we can make.

For example if base is $60$, then $60 = 2^2 \times 3 \times 5$. So we find out $x = \text{factorialPrimePower}(2)$, $y = \text{factorialPrimePower}(3)$ and $z = \text{factorialPrimePower}(5)$. But then, we see that we need $2^2$ in $60$, so we can't use all the $x$ we calculated, we need to pair them. So it becomes $x = \frac{x}{2}$. Now, using $x,y,z$ we can make $60$ only $MIN(x,y,z)$ times. So this will be number of trailing zero.

Summary

We find number of trailing zero using the following steps:
  1. Factorize the base $B$
  2. If $B = p_1^{a_1} \times p_2^{a_2}... \times p_k^{a_k}$, then find out occurance of $x_i =  \text{factorialPrimePower} ( p_i)$.
  3. But we can't use $x_i$ directly. In order to create $B$ we will need to combine each $p_i$ into $p_i^{a_i}$. So we divide each $x_i$ by $a_i$.
  4. Number of trailing zero is $MIN(x_1,x_2,...,x_k)$.

Resources


  1. forthright48 - Number of Digits of Factorial
  2. forthright48 - Prime Factorization of Factorial
  3. forthright48 - Introduction to Number System 
  4. Wikipedia - Trailing Zero

No comments:

Post a Comment

Leave comments for Queries, Bugs and Hugs.