How many trailing Zeros does the result of 1000! have? Brute-force solution with Google Go

14.05.2013
Go
13 comentarios

A lot of tech companies ask interesting questions when they hire employees. One of these questions is: How many trailing zeros are there in 1000! (1 × 2 × 3 × .. × 1000).
As you might imagine, the actual result of 1000! is a rather large number, something you can hardly do in your mind, at least unless you’re some kind of savant.

However, there’s a solution you can come up with that doesn’t need a calculator or anything digital. Spoiler alert: There are certain multiplies that give you a zero at the end. Google knows the answer if you’re wondering how to solve this riddle with a paper and a pen.

I’ve been playing around with Google’s language “Go” for a while and wondered if I could solve this riddle using a more brute-force like solution. The code is rather simple, there’s a factorial function I needed to add because the result is too big for a data type like double or int. I then call that function and count the number of zeros using a simple regex pattern. Something you can do when you’re in an interview but it works as well and is also pretty fast.

package main
 
import "fmt"
import "math/big"
import "regexp"
 
func main() {
	c := int64(1000)
	f := big.NewInt(c)
	s := factorial(f)
	r := regexp.MustCompile(`[0]+$`)
 
	l := r.FindString(s.String())   
	fmt.Printf("There are %d zeros at the end of %d!\n", len(l), c);
}
 
func factorial(n *big.Int) (result *big.Int) {
	result = new(big.Int)
 
	switch n.Cmp(&big.Int{}) {
	case -1, 0:
		result.SetInt64(1)
	default:
		result.Set(n)
		var one big.Int
		one.SetInt64(1)
		result.Mul(result, factorial(n.Sub(n, &one)))
	}
	return
}

13 Comments

Well..at cold I would say:

10, 20,30,…,100 = 11 zeros

following the same logic for the other’s “hundreds”

200, 300, 400, 500, 600, 700, 800, 900, 1000

110 but 1000 has one more zero so: 111 ZEROS?

It’s about the zeros at the end of the number, basically: 1000!=1312312312312313435345645640000 would mean 4 zeros. The number is a lot bigger though.

If you’re only interested in the answer as in how many zeros, the easiest way is to realize that each 0 means a factor of 10. And you can only get 10 by multiplying 2 and 5. 10=2*5, further we know that from 1-1000, there will be more numbers divisible by 2. So you only have to keep track of how many numbers from 1-1000 that are factors of 5 and how many times they factor in.

general solution:

for(int i=1;i<=n;i++)
{
 int current = i;
 while(current > 0)
 {
   if(current%5==0)
   {
     count++;
   }
   current = current/5;
 }
}
return count;

I think you’re missing a few multiplies. Here’s what I’ve got:

int count = 0;
for (int i=1;i<=1000;i++) {
    if (i%5==0) {
     count++; 
    }
    if (i%25==0) {
     count++;  
    }
    if (i%125==0) {
     count++;
    }
    if (i%625==0) {
     count++;  
    }
}
return count;

Your website won’t let me write the code out…It’s removing special characters like greater than and anything after…

so it’s like this:

for(int i=1;i less than or = n;i++)
{
int current = i;
while(current greater than 0)
{
if(current%5==0)
{
count++;
}
current = current/5;
}
}
return count;

Yeah wordpress seems to filter a few things, I’ve updated your first post. Now that I see the actual code, your solution works just fine and is more elegant than what I posted above! Thanks!

Yep. You had it correct too.

A math approach: every number can be decomposed in prime factors; hence every number can written as n = 2^p2 * 3^p3 * 5^p5 * 7^p7 * …, where pi >= 1. Since a zero at the end is made of 2 * 5, this means we have to get the min(p2, p5) = p5 (can be proved by induction). Therefore, the number of zeros is the power of 5 in the prime factorization of n.
The code that does that is fairly simple to write (it’s just a for with an while).
Now comes the complexity part, i.e. what’s the algorithm complexity in terms of Big-O notation.
The inner loop (the while) has the complexity log_5 (i) and over the for the complexity gets sum(log_5(i)). Since log_5(i) <= log_5(n), then the complexity is O(n*log_5(n)). Another way to compute the complexity is by saying that sum (log_5(i)) = integral(1, n) (log_5(x) dx) = integral(1, n) (ln(x)/ln(5)) dx = 1/ln(5)*(n*ln(n) – n + 1) = O(n ln n).

Thanks for your comment! The complexity part is a bit beyond my math knowledge but I’ll try to figure it out myself and compare it to your result. Maybe I’m able to come up with the same solution 😉

Actually, it can be done even easier: the quantity of numbers divisible by X that lay between 1 and N is just N div X (integer part of the division result). So you can do it like this (in C syntax):

int zeroesInFactorial(int n)
{
    int zeroesCount = 0;
    while (n >= 5) {
        zeroesCount += (n = n / 5);
    }
    return zeroesCount;
}

Interesting approach! Never thought about that, thanks for sharing!

Are these interview questions really necessary to determine whether one is eligible for a programming job or not?

For me, having the right attitude takes the number one spot. Knowing how to write clean and efficient code takes number 2. The ability to know the factorial of 1000 takes no spot whatsoever.

Well, whenever I hire someone I don’t ask such questions but I do see some benefit of asking such questions. It’s not about the ability to know the factorial of 1000, you’d have to be some kind of savant to do that and probably lack some social skills. It’s not so much a number thing but rather about problem solving and the ability to come up with some out of the box thinking. It probably also depends on the person you’re looking for – need someone to implement that new shiny UI or looking for someone to come up with a faster algorithm to analyze your audio data?

Personally I just like riddles and challenges which is why I thought I’d solve this thing in an unexpected approach… Just for fun, nothing else (:

CodeBlog.ch

How many trailing Zeros does the result of 1000! have? Brute-force solution with Google Go

13 Comments

Leave a Reply