Click here to Skip to main content
15,844,477 members
Articles / Programming Languages / C++
Tip/Trick

How Many Zeros in a Product of Numbers

Rate me:
Please Sign up or sign in to vote.
4.80/5 (12 votes)
18 Aug 2015CPOL2 min read 28.4K   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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


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

Comments and Discussions

 
QuestionI second the upvote for mathematics fun, but... Pin
Michael Sisco20-Aug-15 8:13
Michael Sisco20-Aug-15 8:13 
I'm pretty sure the num_zeros function could be re-written as:
C#
int num_zeros(int num)
{
    int n = 0;
    int divisor = 5;
    while (divisor <= num)
    {
        n = n + num / divisor;
        divisor = divisor * 5;
    }
    return n;
}

The trick here comes from knowing that the only thing that is really important is how many factors of 5 there are, because the prime factorization of every factorial will have far more factors of 2 than it does factors of 5. (floor(log2(n)) > floor(log5(n)))

Determining the number of factors of 5 boils down to adding one for each multiple of 5 less than n, then adding another one for every multiple of 25 less than n, another for each multiple of 125 less than n, and so on.

I haven't tried it, but I'm reasonably sure that this version would run orders of magnitude faster, simply by applying a little math before we start to write code.

As I said in the subject line, though. I truly applaud the invitation to think about fun math problems. Smile | :) Wink | ;) Smile | :)
Michael Sisco

AnswerRe: I second the upvote for mathematics fun, but... Pin
schollii22-Aug-15 20:04
schollii22-Aug-15 20:04 
SuggestionRe: I second the upvote for mathematics fun, but... Pin
Christophe Van Olmen23-Aug-15 23:19
professionalChristophe Van Olmen23-Aug-15 23:19 
Question[My vote of 1] one point for the invitation to think about mathematics fun Pin
r_alf20-Aug-15 4:33
r_alf20-Aug-15 4:33 
AnswerRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
Comte Olivier20-Aug-15 7:55
Comte Olivier20-Aug-15 7:55 
GeneralRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
Michael Sisco20-Aug-15 8:16
Michael Sisco20-Aug-15 8:16 
GeneralRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
r_alf20-Aug-15 8:51
r_alf20-Aug-15 8:51 
GeneralRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
Comte Olivier20-Aug-15 9:20
Comte Olivier20-Aug-15 9:20 
GeneralRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
r_alf20-Aug-15 9:28
r_alf20-Aug-15 9:28 
GeneralRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
r_alf20-Aug-15 9:53
r_alf20-Aug-15 9:53 
GeneralRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
Comte Olivier20-Aug-15 23:34
Comte Olivier20-Aug-15 23:34 
GeneralRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
r_alf23-Aug-15 9:57
r_alf23-Aug-15 9:57 
AnswerRe: [My vote of 1] one point for the invitation to think about mathematics fun Pin
schollii22-Aug-15 23:49
schollii22-Aug-15 23:49 
AnswerNIce Pin
rainer erdmann19-Aug-15 11:32
rainer erdmann19-Aug-15 11:32 
QuestionVery nice Pin
Amarnath S18-Aug-15 21:51
professionalAmarnath S18-Aug-15 21:51 
GeneralMy vote of 5 Pin
Frank Lindecke18-Aug-15 21:08
Frank Lindecke18-Aug-15 21:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.