Factorial of Large Numbers 96, 97, 98, 100 ...

Factorials grow incredibly fast. 20! still fits in a Java long, but 21! does not, and 100! has 158 digits. So this problem is really about one question: how do you do arithmetic on numbers too big for any built-in type?

Problem

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

Input: an integer t (1 ≤ t ≤ 100), the number of test cases, followed by t lines, each with one integer n (1 ≤ n ≤ 100).
Output: for each n, print n! on its own line.

Input
4
97
98
99
100

Output
96192759682482119853328425949563698712343813919172976158104477319333745612481875498805879175589072651261284189679678167647067832320000000000000000000000
9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Note that the problem is "large" because of the output, not the input. n is at most 100.

Approach 1: BigInteger

Java's java.math.BigInteger stores integers of any size, so the simplest solution is to multiply 1 × 2 × 3 × ... × n with it. In Python, normal integers already have unlimited size, so math.factorial(n) just works.

import java.math.BigInteger;
import java.util.Scanner;

public class Factorial {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            BigInteger result = BigInteger.ONE;
            for (int i = 2; i <= n; i++) {
                result = result.multiply(BigInteger.valueOf(i));
            }
            System.out.println(result);
        }
    }
}

Approach 2: multiply digit by digit

In C or C++, or when the interviewer says "no BigInteger", you do the multiplication the way you learned at school. Store the number as an array of digits, units digit first. To multiply by x, go through the digits from the units upwards: multiply each digit by x, add the carry from the previous step, keep the last digit of the result in place, and carry the rest. When you run out of digits, keep writing out the carry as new digits.

Example: we have 24 stored as [4, 2] and multiply by 5. 4 × 5 = 20, so write 0 and carry 2. Then 2 × 5 + 2 = 12, so write 2 and carry 1. The carry 1 becomes a new digit, giving [0, 2, 1], which read backwards is 120. That is 5!.

import java.util.Scanner;

public class FactorialArray {
    // digits[] holds the number in reverse order: digits[0] is the units digit
    static String factorial(int n) {
        int[] digits = new int[200];        // 100! has 158 digits, so 200 is enough
        digits[0] = 1;
        int len = 1;
        for (int x = 2; x <= n; x++) {
            int carry = 0;
            for (int i = 0; i < len; i++) {
                int prod = digits[i] * x + carry;
                digits[i] = prod % 10;
                carry = prod / 10;
            }
            while (carry > 0) {
                digits[len++] = carry % 10;
                carry /= 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = len - 1; i >= 0; i--) sb.append(digits[i]);
        return sb.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) System.out.println(factorial(sc.nextInt()));
    }
}

Both programs were run on the sample input and produce exactly the output shown above.

Complexity

For n!, the number has about d = n log₁₀n digits, and we multiply it by each of the n values, so the digit-array approach takes about O(n × d) steps. For n = 100 that is roughly 100 × 158, which is tiny. The array of 200 digits is enough for n up to 100, since 100! has 158 digits.

Common mistakes

• Using long or double. long silently overflows after 20!, and double loses precision long before that, so you get the right first few digits and wrong ones after.
• Printing the digit array from the wrong end. We store the units digit first, so it has to be printed in reverse.
• Making the array too small. Count the digits of the biggest answer first: for n ≤ 100, 158 digits.

This is the same problem as SPOJ FCTRL2, if you want to submit it.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More Java solutions All coding problems MCQ practice