Here’s an interesting problem from CodeChef.com:

——–
You are asked to calculate factorials of some small positive integers.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100. Output

For each integer n given at input, display a line with the value of n!

Sample input:
4
1
2
5
3
Sample output:
1
2
120
6
——–

My Solution

The problem looks pretty easy, but a naive implementation of the factorial algorithm didn’t solve all test cases within 1 second, which is the time limit. I then implemented a version with memoization, but still it was not fast enough, and I realized that the 20! was already out of the range of unsigned long long. Using double wouldn’t work either because I would lose precision on the very large numbers.

In order to solve it using C or C++ I would need to either implement a function that would calculate factorials and store the results in arrays, or use a bignum library. I figured it would be faster to just solve it in Java which comes with a built-in class for large integers. The C solution should be fun though, and might implement it in the future.

import java.math.BigInteger;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

  public static void main(String[] args){
    int i,j,x;
    x = 0;
    j = 0;
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try{
      j = Integer.parseInt(br.readLine());
    }
    catch(IOException e){
      e.printStackTrace();
    }
    for(i=0;i<j;i++){
      try{
        x = Integer.parseInt(br.readLine());
      }
      catch(IOException e){
        e.printStackTrace();
      }
      System.out.println(factorial(x));
    }    
  }

  public static BigInteger factorial(int x){
    BigInteger result = new BigInteger("1");
    while(x>0){
      result = result.multiply(new BigInteger(""+x));
      x--;
    }
    return result;
  }

}