How Many Zeros in a Product of Numbers

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.

#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:

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 18^th, 2015: Version 1
• August 23^rd, 2015: Version 2, incorporating comments