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;
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;
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;}
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 (:
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:
I think you’re missing a few multiplies. Here’s what I’ve got:
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):
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 (: