## 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

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

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.