## Microsoft Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

``````public int getZeroes(int n)
{
double m = Math.util.log(n,5);
int result = 0;
for(int i = 0; i < m;i++)
{
result += Math.util.exp(Math.util.exp(m - i), 5);
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0

Could anybody explain to me what the logic here is? as in...the logic in the code?

Comment hidden because of low score. Click to expand.
0
of 0 vote

it 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

Comment hidden because of low score. Click to expand.
0

number_of_trailing_zeros = floor(n/5) + floor(n/5^2) + floor(n/5^3) + ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the formula should be
num_zeros = floor(n/5) + floor(n/5^2) + floor(n/5^3) ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

also since number of factors of 2 cannot exceed the number of factors of 5, its basically number of elements which are factors of the number 5.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The formula to find the trailing zeros is
min (x,y)

where x = floor(n/5) + floor(n/5^2) + floor(n/5^3) + ...
and y =floor(n/2) + floor(n/2^2) + floor(n/2^3) + ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Doesn't all the above solutions, find the num(5) in 'n'??

Shouldn't we be doing it for 'n!'?? Since, we need to find the number of zeros in n!, we need to find num(5) in 'n!'. So, 'n' should be replaced by 'n!' in all the above solutions!

Comment hidden because of low score. Click to expand.
0
of 0 vote

we need not check for whole n! .
moreover finding jus x=floor(n/5) + floor(n/5^2) + floor(n/5^3) + ... is enough
no need to use y =floor(n/2) + floor(n/2^2) + floor(n/2^3) + ... and taking only the min of those two numbers b'cas that case never come wherein x>y as mentioned earlier

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}

Comment hidden because of low score. Click to expand.
0

This is wrong!

``````int z(int num) {
int count = 0, i, hold;
for (i=5; (hold=num/i) > 0; i*=5 )
count += hold;
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Good explanation.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int zeros = n/5; // round down to nearest integer
while(zeros > 0)
{
zeros += zeros/5;
}

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

it should be like:

int num=0, tmp=n;
do{
tmp/=5;
num+=tmp;
}while(tmp>=5);

Comment hidden because of low score. Click to expand.
0
of 0 vote

num/5

Comment hidden because of low score. Click to expand.
0
of 0 vote

floor(n/5)+floor(n/5^2)+... is correct answer I think

Comment hidden because of low score. Click to expand.
0
of 0 vote

A slight variation of the problem is also interesting.
Find number of zeros in n factorial when
1. n is in base 5
2. n is in base 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

any solution for algooz Qs???

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private int getFactTrailingZerosCount(int n) {
double d = (double) n;
int sumPowers = 0;
double pow = 1.0;
while (true) {
double pow5div = Math.floor(d / Math.pow(5, pow));
if (pow5div <= 0.0) {
break;
}
sumPowers += pow5div;
pow += 1.0;
}
return sumPowers;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Above post is to find the number of trailing zeros in 16!, change its values to find for other number.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Above post is to find the number of trailing zeros in 16!, change its values to find for other number.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Above post is to find the number of trailing zeros in 16!, change its values to find for other number.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.