Factorial of a Big Number

Problem

Read n (0 <= n <= 100) and print n! exactly. 100! has 158 digits, so a normal long is not enough.

Constraints

  • 0 <= n <= 100

Examples

Input

25

Output

15511210043330985984000000

Solutions

Best approachTime O(n * digits)Space O(digits)

Normal integer types overflow after 20!. Big integer types grow as needed, so the answer is exact.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Compute n! exactly.
 * Input   : One integer n.
 * Output  : n! as digits.
 * Approach: Use big integers.
 * Time    : O(n * digits)
 * Space   : O(digits)
 * Java    : 8 or newer.
 */
import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String solve(long n) {
        // Step 1: BigInteger can hold any number of digits. Start at 1.
        BigInteger result = BigInteger.ONE;

        // Step 2: Multiply by 2, 3, ..., n.
        for (long i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result.toString();
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. After which n does a 64-bit long overflow for n!?