15,883,278 members
Articles / Programming Languages / C++
Tip/Trick

# How Many Zeros in a Product of Numbers

Rate me:
18 Aug 2015CPOL2 min read 28.7K   5   16
Compute the number of trailing zeros in factorial(N) for any 32-bit integer N > 0

## Introduction

Compute the number of trailing zeros in factorial(N) for any 32-bit integer N > 0. The `num_zeros()` function, below, is easily adaptable to support computation of # of trailing zeros factorial of any 64-bit integer. Some results are shown below:

```Fac(1) = 1 has 0 trailing zeros
Fac(2) = 2 has 0 trailing zeros
Fac(5) = 120 has 1 trailing zeros
Fac(9) = 362880 has 1 trailing zeros
Fac(10) = 3628800 has 2 trailing zeros
Fac(14) = 87178291200 has 2 trailing zeros
Fac(15) = 1307674368000 has 3 trailing zeros
Fac(19) = 121645100408832000 has 3 trailing zeros
Fac(20) = 2432902008176640000 has 4 trailing zeros

Fac(1000) has 249 trailing zeros
Fac(1000000) has 249998 trailing zeros```

## Background

A 64-bit unsigned integer can hold the factorial of up to 20. How would you know how many trailing zeros there are in a factorial of, say, 1000 or 1000000?

## Using the Code

Copy `count_fac()` and `num_zeros()` to your utilities library. Then `num_zeros(N)` where N is any 32-bit int > 0, gives the number of trailing zeros.

C++
```#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

int count_fac(int factor, int num)
{
int count_fac = 0;
while (num / factor == num / float(factor))
{
num = num / factor;
count_fac ++;
}
return count_fac;
}

int num_zeros(int num)
{
int count_fac_2 = 0;
int count_fac_5 = 0;
for (int x=1; x<=num; x++)
{
count_fac_5 += count_fac(5, x);
count_fac_2 += count_fac(2, x);
}

return min(count_fac_2, count_fac_5);
}

uint64_t fac(int num)
{
if (num > 1)
return num * fac(num - 1);
return num;
}

int main()
{
for (int num=1; num<=20; num++)
cout << "Fac(" << num << ") = "
<< fac(num) << " has " << num_zeros(num)
<< " trailing zeros" << endl;

vector<int> large_nums = {1000, 1000000, 1000000000};
for (int large_num: large_nums)
cout << "Fac(" <<
large_num << ") has " << num_zeros(large_num)
<< " trailing zeros" << endl;
}```

## Points of Interest

The trick is to realize that the number of trailing zeros is the number of times the number is divisible by 10, and that two numbers multiplied are divisible by 10 according to how many times their prime factors multiply to produce 10, i.e., the following #times: min (number of times divisible by 2, number of times divisble by 5). For example 125*124: 125=5*5*5, whereas 124=2*2*31 so the product is 2*2*5*5*5*31: there are 2 twos and 3 fives, so there are 2 tens, hence 2 trailing zeros in the product of those numbers.

Some readers have correctly pointed out that some efficiency can be gained by noticing that in the case of factorials, where the product of numbers is 1*2*3*4*...*N, there are always many more 2's than 5's: there is a factor of 2 every second number, whereas there is a factor of 5 every 5 numbers.

However, the approach I used is more generic in that it is trivially extended to handle any set of numbers multiplied, not just sets that correspond to factorials:

C++
```int count_fac(int factor, int num)
{
int count_fac = 0;
while (num % factor == 0)
{
num = num / factor;
count_fac++;
}
return count_fac;
}

#include <list>
using namespace std;

int num_zeros(const list<int>& nums)
{
int count_fac_2 = 0;
int count_fac_5 = 0;
for (int num: nums)
{
count_fac_5 += count_fac(5, num);
count_fac_2 += count_fac(2, num);
}

return min(count_fac_2, count_fac_5);
}```

This produces the following results (`main()` suitably modified to generate random sequences of 14 numbers which are then multiplied.

```Product(3, 4, 5, 13, 16, 27, 30, 35, 36, 41, 42, 49)=1392850094598144000 has 3 trailing zeros
Product(21, 4, 34, 42, 2, 40, 26, 21, 16, 14, 40, 31, 25, 20)=727662226636800000 has 5 trailing zeros
Product(46, 46, 49, 35, 16, 31, 22, 9, 39, 5, 48, 36, 46, 16)=14598889066926964736 has 2 trailing zeros
Product(25, 25, 49, 46, 50, 16, 26, 50, 25, 5, 7, 44, 8, 10)=4512508000000000000 has 12 trailing zeros

Product(1000 random numbers in [1,1000]) has 226 trailing zeros```

To be tested:

The total # of digits that the product has can be computed, without computing the product:

`sum(floor(log(number) + 1))`

In fact, the entire set of digits of the product can be obtained without multiplication because its logarithm base 10 is the sum(log(numbers)). The fractional portion of this sum, when used as a power of 10, will give a number between 1 and 9.99999..... The integer portion of this sum is 1 less than the number of digits, i.e. `int(sum(log(numbers)))+1` = number of digits k of product, and `pow(10, frac(sum(log(numbers))))` has the digits, keep k of them. num_zeros(numbers) of those digits will be 0, so only k - num_zeros(numbers) need to be stored. However, all this relies on floating point arithmetic, whose precision will determine how "deeply" into the number you can trust the digits. I think you should be able to trust the dozen or so most significant digits, and the `num_zeros` count, everything in between will be unreliable.

## History

• August 18th, 2015: Version 1
• August 23rd, 2015: Version 2, incorporating comments

Written By
Software Developer (Senior)
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

 First Prev Next
 I second the upvote for mathematics fun, but... Michael Sisco20-Aug-15 7:13 Michael Sisco 20-Aug-15 7:13
 Re: I second the upvote for mathematics fun, but... schollii22-Aug-15 19:04 schollii 22-Aug-15 19:04
 Re: I second the upvote for mathematics fun, but... Christophe Van Olmen23-Aug-15 22:19 Christophe Van Olmen 23-Aug-15 22:19
 [My vote of 1] one point for the invitation to think about mathematics fun r_alf20-Aug-15 3:33 r_alf 20-Aug-15 3:33
 Re: [My vote of 1] one point for the invitation to think about mathematics fun Comte Olivier20-Aug-15 6:55 Comte Olivier 20-Aug-15 6:55
 Nice catch. Put it together and the function becames: C# ```int num_zeros(int num) { int count_fac_5 = 0; for (int x=5; x<=num; x*=5) count_fac_5 += num/x; return count_fac_5; }```
 Re: [My vote of 1] one point for the invitation to think about mathematics fun Michael Sisco20-Aug-15 7:16 Michael Sisco 20-Aug-15 7:16
 Re: [My vote of 1] one point for the invitation to think about mathematics fun r_alf20-Aug-15 7:51 r_alf 20-Aug-15 7:51
 Re: [My vote of 1] one point for the invitation to think about mathematics fun Comte Olivier20-Aug-15 8:20 Comte Olivier 20-Aug-15 8:20
 Re: [My vote of 1] one point for the invitation to think about mathematics fun r_alf20-Aug-15 8:28 r_alf 20-Aug-15 8:28
 Re: [My vote of 1] one point for the invitation to think about mathematics fun r_alf20-Aug-15 8:53 r_alf 20-Aug-15 8:53
 Re: [My vote of 1] one point for the invitation to think about mathematics fun Comte Olivier20-Aug-15 22:34 Comte Olivier 20-Aug-15 22:34
 Re: [My vote of 1] one point for the invitation to think about mathematics fun r_alf23-Aug-15 8:57 r_alf 23-Aug-15 8:57
 Re: [My vote of 1] one point for the invitation to think about mathematics fun schollii22-Aug-15 22:49 schollii 22-Aug-15 22:49
 NIce rainer erdmann19-Aug-15 10:32 rainer erdmann 19-Aug-15 10:32
 Very nice Amarnath S18-Aug-15 20:51 Amarnath S 18-Aug-15 20:51
 My vote of 5 Frank Lindecke18-Aug-15 20:08 Frank Lindecke 18-Aug-15 20:08
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Apr-24 6:49 Refresh 1