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
Normal integer types overflow after 20!. Big integer types grow as needed, so the answer is exact.
/*
* 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)
- After which n does a 64-bit long overflow for n!?