Jabong Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
This is a implementation:
package src;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
*
* @author smallville
*/
public class ZerosInFactorial {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
String line = br.readLine();
int N = Integer.parseInt(line);
System.out.println("Number of trailing zeroes in "+N+"! are:");
System.out.println(countZeros(N));
}
}
public static int countZeros(int n){
int count5=0;
//int count2=0;
int number=5;
for(int i=1; number<=n; i++) {
count5+=(n/number)*i;
number*=5;
}
return count5;
}
}
The math behind it is that the trailing zeros are produced from multiples of 5 multiplied by multiples of 2. lets say you want to count the number of trailing 0s in 12! (where it is 12*11*10*....*3*2*1).
The trailing zeros will be produced from 5*2 and 10*1 so you have 2 trailing zeros (corresponding to two multiples of 5).
Next when the number is larger than 25 the multiple of 25 produces two traling zeros instead of 1 (4*25 = 100) and accordingly 125(5*5*5) produce 1000 (three trailing zeros) if multiplied by 8.
So the final logic should count the multiples of 5 + number of multiples of 25 + number of multiples of 125 and so on till you reach 5^(n-1) where 5^(n-1) <= your number < 5^(n)
I will take an example to ilustrate
30 !
- take a ctr and increment by 1 since 30 has 1 0
- 29 reject this
- 28 it has 2's 2 and one 9 take a var for count of even
- 27 leave
- 26 1 2 increment even num count
- 25 it has 2 five take in another var
Hence at last number of 0 will be
Var for 0 + min(var if 2 , var of 5)
class NoOfTrailingZeros{
private static int trailingZeroes(int n){
int power = 5;
int i = 1,noOfZeroes = 0;
while(power < n){
noOfZeroes = noOfZeroes + (n/power);
power = power*5;
}
return noOfZeroes;
}
public static void main(String args[]){
int n = 10;
System.out.println(trailingZeroes(n));
}
}
public class TrailingZero {
public static void main(String[] args) {
int a = 15;
System.out.println(trailingZero(getFactorial(a)));
}
private static int getFactorial(int a) {
if(a==1)
return 1;
return a*getFactorial(a-1);
}
private static int trailingZero(int a) {
int count = 0;
char[] ch = new Integer(a).toString().toCharArray();
for(int i=ch.length-1;i>=0;i--){
if(ch[i] == '0'){
count++;
}
else{
break;
}
}
return count;
}
}
#include<stdio.h>
int fact(int fact_num)
{
if(fact_num==0||fact_num==1)
{
return 1;
}
else
{
return fact_num*fact((fact_num-1));
}
}
int main()
{
int i,inp=7,fact_value,reminder,flag,count=0;
fact_value=fact(inp);
while(fact_value!=0)
{
reminder=fact_value%10;
fact_value=fact_value/10;
if(reminder==0)
{
count++;
}
else
{
flag=0;
}
}
if(count>0)
{
printf("The given factorial has %d zeroes",count);
}
else
{
printf("The given factorial doesn't contain zeroes at all");
}
return 0;
}
just use simple mathematics trick...
- Abhishek kumar May 11, 2014n!=[n/5]+[n/5^2]+[n/5^3]+[n/5^4]+....so on..where [ ] represents greatest integer function.
for example we want to calculate no of zeros in 49!
49!=[49/5]+[49/5^2]
=[9.8]+[49/25]
=9+[1.96]
=9+1
=10
so no of zeros in 49 ! is 10..