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

- vairaghi February 23, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- dpooja85 March 01, 2009 | Flag
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

- abybaby January 06, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Caeser February 02, 2008 | Flag
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) ...

- JobCatcher January 06, 2008 | Flag Reply
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.

- choti January 12, 2008 | Flag Reply
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.

- choti January 12, 2008 | Flag Reply
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) + ...

- zara January 17, 2008 | Flag Reply
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!

- khexa January 28, 2008 | Flag Reply
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

- cbitian February 14, 2008 | Flag Reply
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);
}

- gauravk.18 February 17, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Psycho February 15, 2013 | Flag
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.

- Ravi Kant Pandey February 18, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good explanation.

- russoue February 09, 2010 | Flag
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.

- blackpepper February 24, 2008 | Flag Reply
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;
}

- Example March 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it's a dead loop

- dandy May 16, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it should be like:

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

- dandy May 16, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

num/5

- mrx April 09, 2008 | Flag Reply
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

- creepingdog April 25, 2008 | Flag Reply
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

- algooz April 27, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

any solution for algooz Qs???

- desiNerd May 05, 2008 | Flag Reply
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;
  }

- q May 24, 2008 | Flag Reply
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);

}
}

- Arpan March 21, 2009 | Flag Reply
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.

- Arpan March 21, 2009 | Flag Reply
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.

- Arpan March 21, 2009 | Flag Reply
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.

- Arpan March 21, 2009 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More