Microsoft Interview Question
Software Engineer / Developersit can be found as follows
num zeros = floor(n/5) + 2*floor(n/5^2) + 3*floor(n/5^3)...so on
Th logic is straight forward. There will be as many zeros as there are no of 5s in the numbers, as 5 * 2 = 10 and num(5) < num (2)
Note that these 5s also include the multiples of 10. So we don't need extra
logic for them
what is floor here?
Can you plz elaborate?
My algo would be simple
- Take the number check if(n%2==0)cnt1++; else if(n%5==0)cnt2++;
-reduce it by one and do the samething
-when n>=2, then return the min(cnt1,cnt2)
This is because for every '2' ther must be a matching '5' in the factorisation
for Eg: in fact(15)
2' factors - 14,12,10,8,6,4,2 = 7 number of factors
5' factors- 15,10,5 = 3 number of factors
so ther are 3 (5*2) number of trailing zeroes.
bcoz of these three number of factors of 5, you are assured of atleast three number of factors of 2.
Is this right or am I erring somewher.
#include<stdio.h>
void main()
{
int n, no = 0, x = 5, i =1;
printf("Enter the number\n");
scanf("%d", &n);
while(n/x != 0)
{
no = no + n/(5*i);
i = i+5;
x = x *5;
}
printf("The total no. of trailing zeros in the number is %d \n", no);
}
Hi,
As n! = 1*2*3* 4* 5*.... *10* .... *25 *.....125*....*n
We observe every five numbers has one factor of 5 , then every 25 numbers has 1 extra factor of 5 , then every 125 numbers has 1 extra factor of 5 ....
so
int numTrailZeros(int n){
int sum=0;
while(n != 0){
sum=sum + n/5;
n = n/5;
}
return sum;
}
if any problem plz let me know.
floor(n/5) + floor(n/25) + floor(n/125) + ... + floor(n/5^n) + ...
The floor function means round down to the nearest integer.
For example, let's take 5!, or n = 5.
floor(5/5) = floor(1) = 1.
So, 5! ends in 1 zero.
For example: if we want to know the no. of zeros in 100!,
floor(100/5)+floor(100/25) = 20 + 4 = 24.
So, 100! consists of 24 zeros.
import java.io.*;
public class NumberZeroes {
public static void main(String args[]){
int x=0;
int fives=0;
int twos=0;
int tens=0;
for (int i=0; i<=16; i++) {
x=i%10;
if (x==2)
twos=twos+1;
if (x==5)
fives=fives+1;
if (x==0 && i>=10 )
tens=tens+1;
}
x = tens + fives;
System.out.println ("Total Zeros =" + x);
}
}
couple of observations. the numbers which contribute zeros are powers of 2 and powers of 5. say n > 125 then n! = 1.2..4.5....8...25...125..... n. every multiple of 5. has atleast one preciding multiple of 2, every multiple of 25 (5 ^ 2), has a preciding multiple of 4(2 ^ 2).. and so on. So all an multiple of 5, and not of higher powers of 5, will contribute one zero (2 * 5), multiple of 25 will contribute 2 (4 * 25 = 100),multiple of 125 will contribute 3, (125 * 8 = 1000) and so on.
so every multiple of 5, contributes a zero, every multiple of 25 will contribute one more(in addition to the the 5 contributed), 125 will contribute one more (in addition to 5 and 25s).
so the code for this would be
- vairaghi February 23, 2008