Published 2022-02-24

Big Factorial

This problem basically asks you to calculate the factorial of a number up to 100. Now, I guess most of you know what a "factorial" is. For those who don't, the factorial of a number N is 1*2*...*N. This problem would be very simple, had it not been for the maximum value of N.Now, the maximum number that we can store in an unsigned 32 bit integer is 2 ^ 32 - 1 and in an unsigned 64 bit integer is 2 ^ 64 - 1. Something like 100!('!' is the notation for factorial) has over 150 decimal digits. The data types mentioned earlier can store numbers having at most 9 and 19 decimal digits respectively. So, we need to find a way to store the 150+ digits that we will get as the answer.

                                
                                    import java.util.Scanner;

/**
 * Program to find factorial for n, where 1 <= n <= 100. Solution for codechef.com
 * 
 * @author Amit Kumar (allyamit@gmail.com)
 * @since 28-May-2017
 */
public class Main {

  // this stores the result limit
  private final static int M_INDEX = 199;

  public static void main(String[] args) {
    try {
      Scanner scan = new Scanner(System.in);
      Integer times = scan.nextInt();
      int inputNumbers[] = new int[100];
      for (int i = 0; i < times; i++) {
        inputNumbers[i] = scan.nextInt();
      }
      for (int i = 0; i < times; i++) {
        display(factorial(inputNumbers[i]));
        System.out.println();
      }
      scan.close();
    } catch (Exception e) {
      System.out.println(e.getMessage());
    }
  }

  /** Convert the number into array integer. */
  private static int[] convertNumberToArray(int x) {
    int[] number = new int[200];
    int index = 0;
    int lastDigit;
    // Store x number into result
    while (x > 0) {
      lastDigit = x % 10;
      number[index] = lastDigit;
      x /= 10;
      index++;
    }
    number[M_INDEX] = index;
    return number;
  }

  /** Multiply the BigNumber generated with the second number. */
  private static int[] multiply(int[] x, int y) {
    int[] result = new int[200];
    int singleDigitMultiplyResult;
    int carry = 0;
    int resultIndex = 0;
    int lastDigit;
    for (int i = 0; i < x[M_INDEX]; i++) {
      singleDigitMultiplyResult = (x[i] * y) + carry;
      lastDigit = (singleDigitMultiplyResult) % 10;
      carry = singleDigitMultiplyResult / 10;
      result[resultIndex] = lastDigit;
      resultIndex++;
    }

    int[] car = convertNumberToArray(carry);
    for (int i = 0; i < car[M_INDEX]; i++) {
      result[resultIndex] = car[i];
      resultIndex++;
    }

    result[M_INDEX] = resultIndex;
    return result;
  }

  /** Find the factorial */
  private static int[] factorial(int n) {
    if (n == 1)
      return convertNumberToArray(1);
    return multiply(factorial(n - 1), n);
  }

  /** Display the result in the codechef.com format */
  private static void display(int[] result) {
    for (int i = result[M_INDEX] - 1; i >= 0; i--) {
      System.out.print(result[i]);
    }
  }
}