I am trying to calculate the factorial, like take an example 5!
5 * 4 * 3 * 2 * 1 = 120 right
20 * 3 * 2 * 1
60 * 2 * 1
120 * 1
120
How to apply this logic in code? I tried this:
int sum = 0;
int num = 5;
for (int i = 1; i <= num; i )
{
sum = num * (num - 1)
I know this is wrong for for loop but if I use this I get the 5 * 4 = 20 for the first iteration
Or:
sum = 1;
sum = sum * (num - i)
It gives like this:
1 = 1 * 4 = 4;
4 = 4 * 3 = 12;
12 = 12 * 2 = 24
24 = 24 * 1 = 24
CodePudding user response:
This can be solved pretty easily with recursion. Essentially, n! is the same as n * (n-1)!. You can use this information to build a simple recursive function to solve the problem. Ex:
public static int factorial(int n) {
if(n == 1) return 1;
return n * factorial(n - 1);
}
The base case is when n = 1, since 1! is 1.
CodePudding user response:
Here is how I would do it. Since factorials can get quite large,
I'm using a BigInteger
. And to expedite computations I am saving previously computed factorials. This is known as memoization
.
System.out.println(fact(1));
System.out.println(fact(0));
System.out.println(fact(15));
System.out.println(fact(20));
System.out.println(fact(22));
System.out.println(fact(15));
System.out.println(fact(21));
System.out.println(fact(22));
System.out.println(fact(23));
prints
1
1
1307674368000
2432902008176640000
1124000727777607680000
1307674368000
51090942171709440000
1124000727777607680000
25852016738884976640000
Nothing too elaborate here
- declare a static list to hold previously computed factorials.
- check if n >= 0
- see if the the factorial has been computed. If so return it.
- otherwise, start with the last computed and continue.
- save each subequently computed factorial
- when finished, return the result.
static List<BigInteger> computedFactorials =
new ArrayList<>(List.of(BigInteger.ONE, BigInteger.ONE));
public static BigInteger fact(int n) {
if (n < 0) {
throw new IllegalArgumentException("n must be >= 0");
}
if (computedFactorials.size() > n) {
// System.out.println("successful lookup");
return computedFactorials.get(n);
}
int k = computedFactorials.size() - 1;
BigInteger fact = computedFactorials.get(k);
for (int i = k 1; i <= n; i ) {
fact = fact.multiply(BigInteger.valueOf(i));
// System.out.println("i = " i ", fact = " fact);
computedFactorials.add(fact);
}
return fact;
}
If you want to see the method in action, just uncomment the two print statements. The downside here is that the list needs to be recomputed each time the program is run. It would be better to save this to a data base on a serialized list. But it may also be overkill based on your specific needs. It could easily be retrofitted to use ints
or longs
.