How many zero total in 100 factorial

Question

I have a homework that count total zero in n factorial. What should i do? I only find way to count trailing of factorial

static int findTrailingZeros(int n) 
{ 
    // Initialize result 
    int count = 0; 

    // Keep dividing n by powers  
    // of 5 and update count 
    for (int i = 5; n / i >= 1; i *= 5) 
        count += n / i; 

    return count; 
} 

Answer 1

The total number of zeros in n! is given by sequence A027869 in the On-line Encyclopedia of Integer Sequences. There really seems to be no way to compute the total number of zeros in n! short of computing n! and counting the number of zeros. With a big int library, this is easy enough. A simple Python example:

import math

def zeros(n): return str(math.factorial(n)).count('0')

So, for example, zeros(100) evaluates to 30. For larger n you might want to skip the relatively expensive conversion to a string and get the 0-count arithmetically by repeatedly dividing by 10.

As you have noted, it is far easier to compute the number of trailing zeros. Your code, in Python, is essentially:

def trailing_zeros(n):
    count = 0
    p = 5
    while p <= n:
        count += n//p
        p *= 5
    return count

As a heuristic way to estimate the total number of zeros, you can first count the number of trailing zeros, subtract that from the number of digits in n!, subtract an additional 2 from this difference (since neither the first digit of n! nor the final digit before the trailing zeros are candidate positions for non-trailing zeros) and guess that 1/10 of these digits will in fact be zeros. You can use Stirling's formula to estimate the number of digits in n!:

def num_digits(n):
    #uses Striling's formula to estimate the number of digits in n!
    #this formula, known as, Kamenetsky's formula, gives the exact count below 5*10^7
    if n == 0:
        return 1
    else:
        return math.ceil(math.log10(2*math.pi*n)/2 + n *(math.log10(n/math.e)))

Hence:

def est_zeros(n):
    #first compute the number of candidate postions for non-trailing zerpos:
    internal_digits = max(0,num_digits(n) - trailing_zeros(n) - 2)
    return trailing_zeros(n) + internal_digits//10 

For example est_zeros(100) evaluates to 37, which isn't very good, but then there is no reason to think that this estimation is any better than asymptotic (though proving that it is asymptotically correct would be very difficult, I don't actually know if it is). For larger numbers it seems to give reasonable results. For example zeros(10000) == 5803 and est_zeros == 5814.

Answer 2

How about this then.

count = 0
s = str(fact)
for i in s:
    if i=="0":
        count +=1
print(count)

Answer 3

100! is a big number:

100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

To be more precise it need ~525 bit and can not be computed without some form of bigint math.

However trailing zeros might be computable on normal integers:

The idea is to limit the result to still fit into your data type. So after each iteration test if the result is divisible by 10. If it is increment your zeros counter and divide the result by 10 while you can. The same goes for any primes except those that divide 10 so not: 2,5 (but without incrementing your zeros counter). This way you will have small sub-result and count of trailing zeros.

So if you do a 2,5 factorization of all the multiplicants in n! the min of the both exponents of 2,5 will be the number of trailing zeros as each pair produces one zero digit (2*5 = 10). If you realize that exponent of 5 is always smaller or equal than exponent of 2 its enough to do the factorization of 5 (just like you do in your updated code).

int fact_trailing_zeros(int n)
    {
    int i,n5;
    for (n5=0,i=5;n>=i;i*=5) n5+=n/i;
    return n5;
    }

With results:

Trailing zeors of n!
       10! :         2
      100! :        24
     1000! :       249
    10000! :      2499
   100000! :     24999
  1000000! :    249998
 10000000! :   2499999
100000000! :  24999999
[   0.937 ms]

However 100! contains also non trailing zeros and to compute those I see no other way than compute the real thing on a bigint math ... but that does not mean there is no workaround like for trailing zeros...

If it helps here are computed factorials up to 128! so you can check your results:

• Fast exact bigint factorial

In case n is bounded to small enough value you can use LUT holding all the factorials up to the limit as strings or BCD and just count the zeros from there... or even have just the final results as a LUT ...

Answer 4

Here some bad code, but it works. You have to use TrailingZeros() only

    public static int TrailingZeros(int n)
    {
        var fac = Factorial(n);
        var num = SplitNumber(fac);
        Array.Reverse(num);
        int i = 0;
        int res = 0;

        while (num[i] == 0)
        {
            if (num[i] == 0)
            {
                res++;
            }
            i++;
        }
        return res;
    }
    public static BigInteger Factorial(int number)
    {
        BigInteger factorial = 1;   // значение факториала

        for (int i = 2; i <= number; i++) 
        {
            factorial = factorial * i;
        }
        return factorial;
    }

    
    public static int[] SplitNumber(BigInteger number)
    {
        var result = new int[0];
        int count = 0;

        while (number > 0)
        {
            Array.Resize(ref result, count + 1);
            result[count] = (int)(number % 10);
            number = number / 10;
            count++;
        }
        Array.Reverse(result);
        return result;
    }