In this post, we’ll see how to count the trailing zeros in a factorial. We’ll start with a short definition of the problem. Then we’ll show an algorithm to calculate them and finally implement it in C.

The widget below is an example implementation. It will return the trailing zeros for the factorial of a number in any base between 2 and 256. In order to avoid too extensive calculations, it’s limited to numbers less than one million. Note that the number is expressed initially in decimals (base 10). Invalid input will return `-1`.

Zeros: 0

## Trailing zeros in a factorial

The factorial of a number (`n!`) is the multiplication of all the numbers less than or equal to that number:

n! = n * (n -1) * … * 1

What we’ll do in this post is to calculate the trailing zeros of `n!`. For example, `15!` equals `1307674368000`, which means it has `3` trailing zeros.

Additionally, the trailing zeros will be calculated for a specific base. The calculations above, for example, were done on base `10` (decimal numbers).

Some common bases are:

• `2` (binary numbers).
• `8` (octal numbers).
• And `16` (hexadecimal numbers).

## Counting trailing zeros algorithm

To simplify this explanation, let’s consider only decimal numbers first.

Retaking the example above, we had that `15!` equals `1307674368000`. Once the factorial has been calculated, it’s straight-forward getting the number of trailing zeros. However, calculating a factorial is a computation-intensive process that grows very rapidly. For example, `100!` is already more than 150 digits long.

Since we don’t really care about the factorial value but only about its trailing zeros, we’ll see how to count the trailing zeros without calculating the factorial.

See that `15!` can be expressed as:

15! = someValue * 10^3

Where `someValue` is some number irrelevant for us. The important part is that the factorial contains three factors of `10`. Each trailing zero is a factor of `10` that can be factored from the factorial. Since `15!` contains three `10` factors, it has 3 trailing zeros.

This means that the number of trailing zeros equals the number of times we can factor `10` from the factorial.

In more general terms:

The factorial of a number `n` in base `b` has as many trailing zeros as factors of `b` that can be factored from `n!`.

Once again: we can factor `10` (the base), `3` times from `15!`. Thus the number of trailing zeros in `15!` is `3`.

This is the algorithm that we’ll use to count trailing zeros in a factorial.

## Implementation: counting trailing zeros in a factorial

The first step will be to get the prime factors of the `base` (which is passed as an argument). Since we’re limiting the base to a maximum of 256, we’ll need only the prime numbers less than this value. To avoid using an extra function to calculate prime numers, we’ll use a pre-calculated list of primes less than 256 (`primes`).

```#define SIZE 54

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251};

int i, n;
int primeCount[SIZE] = {0};

for (n=base, i=0; n != 1 && i<SIZE; i++) {
while (n % primes[i] == 0) {
n /= primes[i];
primeCount[i]++;
}
} ```

`SIZE` is the length of the `primes` array: `54`. The count of prime factors in the base are stored in the `primeCount` array. The factor count of prime number `prime[i]` is stored at the corresponding index in the prime count array:`primeCount[i]`.

Next, for each prime factor of the `base`, we’ll count how many times it can be factored from the factorial of `number` (passed as an argument). We’ll divide that factor count in the factorial by the factor count in the base calculated in `primeCount`. The lesser of these divisions for all factors in the `base` is the number of trailing zeros.

For example, let’s say the base is `45` = `3*3*5`. The prime factors are `3` and `5`. However, the factor count of prime factor `3` is `2` while the factor count of `5` is only `1`. This means that to factor `45` from the factorial, we’ll need twice as many factors of `3` than factors of `5`.

```int factorCount, minCount=-1;

for (i=0; i<SIZE; i++)
if (primeCount[i] != 0) {
factorCount = getFactorialFactorCount(number, primes[i]) / primeCount[i];
if (minCount == -1)
minCount = factorCount;
if (factorCount < minCount)
minCount = factorCount;
}```

The value of `minCount` is initialized to -1. It’s then replaced by the first `factorCount` calculated. Every time a lower value is found, the value of `minCount` is updated. Once the loop finishes, the value of `minCount` is the actual number of trailing zeros in the factorial.

To make the last calculation, we used a helper function `getFactorialFactorCount`:

```int getFactorialFactorCount(int number, int prime)
{
int n, count, factor;

for (count=0, n=2; n<=number; n++)
for (factor=n; factor % prime == 0; factor /= prime, count++)
;

return count;
}```

This function will calculate the number of times we can factor `prime` from the factorial of `number`.

And that’s it!

Putting all of the pieces together we have:

```#include <stdio.h>

#define SIZE 54

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251};

int zeros(int base, int number);
int getFactorialFactorCount(int number, int prime);

int main()
{
int zeroCount;

zeroCount = zeros(8, 64);
printf("There are %d zeros.\n", zeroCount);

return 0;
}

int zeros(int base, int number)
{
int i, n, minCount=-1, factorCount;
int primeCount[SIZE] = {0};

for (n=base, i=0; n != 1 && i<SIZE; i++) {
while (n % primes[i] == 0) {
n /= primes[i];
primeCount[i]++;
}
}

for (i=0; i<SIZE; i++)
if (primeCount[i] != 0) {
factorCount = getFactorialFactorCount(number, primes[i]) / primeCount[i];
if (minCount == -1)
minCount = factorCount;
if (factorCount < minCount)
minCount = factorCount;
}

return minCount;
}

int getFactorialFactorCount(int number, int prime)
{
int n, count, factor;

for (count=0, n=2; n<=number; n++)
for (factor=n; factor % prime == 0; factor /= prime, count++)
;

return count;
}```

We compile the code above to calculate the number of trailing zeros in the factorial of `64` in base `8` as an example. We get:

```\$ gcc factorialtail.c -o main
\$ ./main
There are 21 zeros
```

With this, we have concluded this explanation of how to calculate the number of trailing zeros of the factorial of a number in a certain base.

Published inProgramming
Subscribe
Notify of 