How Many Zeros at the end of 1024!?

This was an interview question from Google. The difficulty is entry level.

The question asks how many zeros are there for the numerical result of 1024!, which is 1 * 2 * 3 * 4 … 1024

The first thought would be the brute-force, which computes the results using arrays (standard data types cannot hold such a big number). However, this is really inefficient because we don’t really care the final number. Allocation of the array is wasting time and space.

The second thought would be to count the divisor factors of 5 and 2. Each zero is generated by a ten which is made up of 5 and 2. The number of 2 factors is way larger than 5, therefore we have to consider only the number of 5 factor, which is the answer.

You can also consider the number of 10 and 2, but choosing 5 is the easiest.

Considering implementation, you can optimise the O(n^2) to O(n) by computing the number of division factor 5.

#!/usr/bin/env python
# https://codingforspeed.com

def count00(x):
    y = 0
    for i in xrange(5, x + 1):
        while i % 5 == 0:
            i /= 5
            y += 1
    return y

def count01(x):
    y = 0
    k = 5
    while k < x:
        y += x / k
        k *= 5
    return y

print count00(1024)
print count01(1024)

Both implementation prints the answer 253. However, the count01 is more efficient than count00.

–EOF (The Ultimate Computing & Technology Blog) —