How to calculate a factorial
Short answer
The factorial n! is the product of the numbers from 1 to n. Use long, because the values grow very fast:
long factorial(int n) {
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
void main() {
IO.println(factorial(5));
IO.println(factorial(20));
}Output:
120
2432902008176640000With recursion
The classic definition: n! = n × (n − 1)!, and 0! = 1:
long factorial(int n) {
return n <= 1 ? 1 : n * factorial(n - 1);
}
void main() {
IO.println(factorial(10));
}Output:
3628800Large values
21! no longer fits into a long. Large values need BigInteger:
BigInteger factorial(int n) {
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
void main() {
IO.println(factorial(30));
}Output:
265252859812191058636308480000000Common mistake
Missing the overflow. A long silently wraps around, and 21! comes out negative:
void main() {
long result = 1;
for (int i = 2; i <= 21; i++) {
result *= i;
}
IO.println(result);
}Output:
-4249290049419214848To catch the overflow, use Math.multiplyExact() — it throws an ArithmeticException.
Functions used in this recipe
- BigInteger — An integer of any size — for when even long is not enough.
- IntStream.range() — Creates a stream of integers from a range.
- ArithmeticException — Thrown on an invalid arithmetic operation, such as integer division by zero.