SPOJ Factorial Problem

I am trying to develop code for SPOJ factorial problem number 11. The following is my code

import java.math.*; 
import java.io.*;
public class Problem11 {

/**
 * Count the number of zeroes at the end of 
 * the factorial value of a number.
 */
public static void main(String[] args) throws IOException
{
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 int numOfInputs=0;
 numOfInputs=Integer.parseInt(br.readLine());
 BigInteger nextNum[]=new BigInteger[numOfInputs];
 BigInteger factValue[]=new BigInteger[numOfInputs];

 //Get all the numbers to be computed
 for(int count=0;count<numOfInputs;count++)
 {
    nextNum[count]=new BigInteger(br.readLine());
 }

 //Obtain the factorial value for each number
 for(int count=0;count<numOfInputs;count++)
 {
     factValue[count]=getFact(nextNum[count]);
 }

 //Obtain the number of trailing zeroes
 for(int count开发者_高级运维=0;count<numOfInputs;count++)
 {
     //System.out.println(factValue[count]);
     System.out.println(getZeroes(factValue[count]));

 }
}


public static String getZeroes(BigInteger num) 
 {
    int numOfZeroes=0;
    while(num.remainder(BigInteger.TEN).equals(BigInteger.ZERO))
    {
        num=num.divide(BigInteger.TEN);
        numOfZeroes++;
    }
    return String.valueOf(numOfZeroes);
 }



public static BigInteger getFact(BigInteger num) 
{
    BigInteger factorial=BigInteger.ONE;    
    if(num.equals(0))
    {
      return (BigInteger.valueOf(1));
    }
    else
    {
        int count=1;
        while((BigInteger.valueOf(count).compareTo(num))<=0)        
        {               
            factorial=factorial.multiply(BigInteger.valueOf(count));
            count++;
        }
    }

    return factorial;

}

}

The code works fine for numbers up to 5 digits with small delay and for the last number 8735373 it is taking too much time, if I submit my solution, the judge shows compilation error.. I am unable to figure out whats the error. Please have a look at my code and help me to trace the problem.

You might look at this method for finding the number of trailing zeros in n!.

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        for (int i = 0; i < count; i++) {
            int n = in.nextInt();
            int result = 0;
            for (int d = 5; d <= n; d *= 5) {
                result += n / d;
            }
            System.out.println(result);
        }
    }
}

Your approach (naive: counting the real factorial value and then counting the zeros manually) would NEVER pass no matter how. Take a look at the extreme case (i.e. upper limit of the factorial, I don't even think the given memory limit is enough to compute it). Look at the problem from different way, think what the real problem is, that's the art of problem solving ;)

Hint: what can produce and add more 0s to the end of a number, specifically by multiplication?

The reason for your error is it should be public class Main

Also your code will get TLE, you must observe that brute force will never work on SPOJ. The way to solve this is to see an interesting pattern with powers of 5 and the number of zeroes at the end.

Here is a solution in C. We don't need to compute the exact factorial for this problem.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 1000000
int xpn(int x, int n){
int prod=1;
while(n){
prod*=x;
n--;
}
return prod;
}
int trail(int x){
int numZero=0;
int i=1;
int k;
for(;x/xpn(5,i);i++){
numZero+=(x/xpn(5,i));
}
return numZero;
}
int main(int argc, char **argv){
#if 1
int n;
int num[MAX];
int zero[MAX];
scanf("%d",&n);
int count=n;
int i=0;
while(count){
scanf("%d",&num[i]);
zero[i]=trail(num[i]);
printf("%d\n",zero[i]);
i++;
count--;
}
#endif
return 0;
}

import java.util.*;
import java.lang.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();
        while (t-->0){
            int n = s.nextInt();
            int count = 0;
            while(n>0){
                count +=n/5;
                n/=5;
            }
            System.out.println(count);
        }

    }
}

This solution will work absolutely fine. Let me explain it. When you refer to quantitative aptitude there is a short formula for calculating the number of trailing zeroes for any factorial number. Divide the number directly by 5 and start adding quotient and then divide quotient with 5 and again add until the value start giving constant quotient. Refer to below example. If you don't even understand refer to quantitative aptitude from any source.

e.g.

1. 60!  60/5 = 12, 12/5 = 2, add all the quotient i.e equals to 14.
2. 500! 500/5 = 100, 100/5 = 20, 20/5 = 4, ans = 124.