Today we're going to talk about factorials and the most common ways to find factorial. This is one of the most basic functions that a programmer needs to both know and be able to work with. Well, let's get started.
The factorial of the number n, denoted as n!, is the value of the product (multiplication) of all natural numbers from 1 to n.
Here's what it looks like (let’s refresh your knowledge of math):
1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24
5! = 1 * 2 * 3 * 4 * 5 = 120
And there's one more small rule for 0:
!0 = 1
If we want to calculate the difference between 6! and 4!:
6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696
Let's see what this would look like when implemented in programming. We'll explore a few ways of how to do calculations of factorial in Java.Ordinary solution in factorial program
Here’s a simple factorial program using loop:
class FactorialExample{
public static void main(String args[]){
int i,fact=1;
int number=7;// our number to do the necessary calculations in class Factorial
for(i=1;i<=number;i++){
fact=fact*i;
}
System.out.println("Factorial of "+number+" is: "+fact);
}
}
Our output on console will be:
Factorial of 7 is: 5040
And one more example to sort things out:
public static int getFactorial(int f) {
int result = 1;
for (int i = 1; i <= f; i++) {
result = result * i; // finding factorial of number using loops
}
return result;
}
Nothing difficult here: we use the passed number as the size of our loop, in which we multiply by all the previous numbers until we get to f. And in main:
System.out.println(getFactorial(6) - getFactorial(4));
Testing the code, we see that we get the desired result: 696.Recursive solution
Recursion happens when a method calls itself. Such a method is called a recursive method. As a rule, it consists of two parts:- A terminating condition — when the terminating condition is satisfied, the method should stop calling itself and start passing values up. After all, if there is no terminating condition, then we will have an infinite loop, with the method calling itself repeatedly until we get a StackOverflowError.
- Whatever logic the situation requires plus a recursive call, but with a different input value.
public static int getFactorial(int f) { // finding factorial of number using recursive solution
if (f <= 1) {
return 1;
}
else {
return f * getFactorial(f - 1);
}
}
Our recursion terminating condition will be when we reach 1. If the parameter is not 1, then we multiply the current value by the result of the next recursive call to the method (to which we pass the current value minus 1).
Solution with a Stream
Anyone unfamiliar with Java's Stream functionality, or anyone who wants to refresh their memory, will benefit from reading about here.
public static int getFactorial(int f) { // finding factorial of number using Stream
if (f <= 1) {
return 1;
}
else {
return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
}
}
Here we use the special IntStream class, which gives us additional capabilities when working with a stream of int values. To create such a stream, we use its static rangeClosed method, which generates values from 2 to f, inclusive, in increments of 1. Next, we use the reduce method to combine all the values. More specifically, we show it how we want to combine the values. Finally, we get the resulting value using the terminal getAsInt method.Using BigInteger
In Java, the BigInteger class is often used to handle numbers, especially BIG numbers. Indeed, if we use int, then the maximum factorial that we can handle without data loss is 31. For the long data type, the maximum factorial is 39. But what if we need the factorial of 100? Let's adapt the previous solutions to BigInteger.Ordinary solution
public static BigInteger getFactorial(int f) { // finding factorial of number using BigInteger
BigInteger result = BigInteger.ONE;
for (int i = 1; i <= f; i++)
result = result.multiply(BigInteger.valueOf(i));
return result;
}
The algorithm is essentially the same, but here we use BigInteger's capabilities: BigInteger.ONE is the starting value 1, and multiply() is used to multiply the previous factorial value and the current number.Recursive solution
public static BigInteger getFactorial(int f) {
if (f <= 1) {
return BigInteger.valueOf(1);
}
else {
return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
}
}
The general logic of the solution does not change, except that some methods are added for working with BigInteger.Solution with a Stream
public static BigInteger getFactorial(int f) {
if (f < 2) {
return BigInteger.valueOf(1);
}
else {
return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
}
}
Everything is essentially same, but with BigInteger. The Stream class gives us the mapToObj method, which we use to convert int values to BigInteger in order to then multiply them with themselves using the multiply method (and get() was added to get an object from the Optional wrapper).
If we run any of these three methods with an argument of 100, then we will avoid a stack overflow and get the correct result:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
GO TO FULL VERSION