## Zillow Interview Question for Software Engineer / Developers

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

The no. of trailing zeros is equal to the number of 5s that are occur as a factor in a number, present in the sequence n! = n.n-1.n-2.....1.1. Example 50 has two 5s (factors) i.e. observed from factors(50) = 2.5.5 OR factors(10) has one 5 i.e. observed from 10 = 2.5

In order to find the no. of such cases where 5 occurs as a factor, we take n/5. This gives us the no. of occurances of 5 as a factor, but it does not give us the exact number of 5s. For example, it will count that 5 occured (is a factor) in 25, but it will not tell us that 5 occured twice in 25 or thrice in 125.

So, to cover this case, we find n/25, and this tells us the number of cases where 25 occurs. But it will not tell the number of times 25 occurs in a given number.

This can be generalized, and we can say, to find the number of cases where 5 occurs, 25 occurs,...5^i occurs. Sum it up to get the answer.

Let us take an example.

50

50/5 = 10, as it occurs in 5, 10, 15, 20, 25, 30, 35, 40, 45, 50

50/25 = 2, as it occurs in 25 and 50

So, our sum is 10 + 2 = 12 ~ Number of trailing zeros.

We can take 5^i for the case where n < 5^i. In our example, we cannot take 5^3 (125), since 125 > 50. Therefore, our summation(50/5^i) = 12, where i = 1, 2

Hope that helps.

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

thanks!!!

Comment hidden because of low score. Click to expand.
1
of 1 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.
1
of 1 vote

The code works fine

``````/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package trailingzeros;

import java.util.Scanner;

/**
*
* @author Sushant
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
int n;
int i = 0, x = 5;
int trailZero = 0;
Scanner sc = new Scanner(System.in);
System.out.println("Enter any factorial number to find trailing zeros.");
n = sc.nextInt();
//for(int i = 1 ; i <=n ; i++)
while(x < n)
{
trailZero += n / x;
x = x*5;
}
System.out.println("Trailing zeros = "+trailZero);
}

}``````

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

My Ans: Summation of (n/5^i), where i = 1,...,k such that 5^(k+1) > n

Does anyone has a better solution ?

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

Soln: Summation(n/5^i), i = 1, 2..k such that 5^(k+1) > n

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

can u please explain hw it has been derived ?

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

Welcome !

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

the best way to find x^k in n! where x is prime is
equal to:
[n/x^1]+[n/x^2]+[n/x^3].....until x^p>n
where [n/x^i] is integer value came after deviding n by x^i;
So for the above problem
say 100!
value=[100/5]+100/25+100/125
=20+4+0
=24
so 5^24 is the max power of 5 which devides 100! or there are 24 trailing zero's in 100!

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

great explanation
http://www.purplemath.com/modules/factzero.htm

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

The number of zero on the tail of n! is the number prime factor of 5 of n!

``````public static int tailZeros(int n) {
int powOf5 = 0;
int c = n;
while(c > 0) {
powOf5 += c / 5;
c /= 5;
}
return powOf5;
}``````

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

``````// Idea:  find how many numbers divisible by 2 and 5 are from
// 1 to n. Since there're always more numbers divisible by 2 than 5,
// we just need to count how many are divisible by 5
unsigned int GetNumberOfTrailingZeroes(unsigned int n)
{
unsigned int uZeroesCount = 0;

for (unsigned int i = n; i > 0; i /= 5)
{
uZeroesCount += i/5;
}

return uZeroesCount;
}``````

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