# How to Calculate the Factorial of a given number

Factorial of a given number can be defined as the product of the given number with all the other numbers which are smaller than the number but greater than zero.

## Example

Let’s generalize it –

But if we want to find the factorial of a large number, say 100, its factorial contains 158 characters, which is impossible to store even with initializing the answer variable with long long int so what’s the solution? The solution is to either use an ArrayList or LinkedList to store the answer and find the factorial of the number using the carry forward approach which is an optimized approach for finding the factorial of a number.

In this blog, we will learn how to print the factorial of a large number using the carry forward approach. But before that, we have to understand the basic code for finding the factorial of small numbers. We will be using two easy methods for that and after understanding them we will move to our initial solution which is to find the factorial of a large number.

## Index

1. Using Iterative Approach
2. Using Recursion Approach
3.  Using Carry-Over Approach – for large numbers
1. Using Array
2. Using ArrayList
4. FAQ

## Using Iterative Approach

The idea behind this approach is simple, make use of the generalized formula we saw in the above sections.

### Algorithm

1. Multiply the given integer with the other positive numbers smaller than it using for loop.
2. Store the values in a different variable.
3. Print the last stored value as it is the factorial of that number.
JAVA
```package com.Tekolio.Extras;

public class Factorial {
public static void main(String[] args) {
int A = 10;
System.out.print("Factorial of " + A + " is " + fact(A));
}
public static int fact(int A) {
int ans = 1;
for(int i=1; i<=A; i++) {
ans = ans * i;
}
return ans;
}
}
```
C++
```#include <iostream>
using namespace std;

// function to find factorial of given number
unsigned int factorial(unsigned int n)
{
int ans = 1;
for (int i = 1; i <= n; i++)
ans *= i;
return ans;
}

// Driver code
int main()
{
int num = 10;
cout << "Factorial of " << num << " is " << factorial(num) << endl;
return 0;
}
```
Python
```def factorial(n):

res = 1

for i in range(2, n+1):
res *= i
return res

# Driver Code
num = 10;
print("Factorial of", num, "is",
factorial(num))
```

## Output

Factorial of 10 is 3628800

Time Complexity: O(n)

Auxiliary Space: O(1)

## Using Recursive Approach

We all know recursive functions are those functions that can call themselves indefinitely until the base case is triggered which will stop it from going into an infinite loop.

We also know from the generic factorial formula that factorial is simply the product of numbers in their descending order until they have reached 1, this is enough to make a recursive call. Let’s see how

### Algorithm

1. Base Case: if the number is equal to 0 or 1, simply return 1.
2. Recursive Step: returns the product of n with the result of calling factorial with an argument equal to n – 1.
JAVA
```package com.Tekolio.Extras;

public class Factorial {
public static void main(String[] args) {
int A = 10;
System.out.print("Factorial of " + A + " is " + fact(A));
}
public static int fact(int A) {
if(A == 1 || A == 0) return 1;
return A * fact(A-1);
}
}

```
C++
```#include <iostream>
using namespace std;

// Function to find factorial
// of given number
unsigned int factorial(unsigned int n)
{
if (n == 0 || n == 1)
return 1;
return n * factorial(n - 1);
}

// Driver code
int main()
{
int num = 10;
cout << "Factorial of "
<< num << " is " << factorial(num) << endl;
return 0;
}
```
Python
```def factorial(n):

if n == 0:
return 1

return n * factorial(n-1)

# Driver Code
num = 10;
print("Factorial of", num, "is",
factorial(num))
```

## Output

Factorial of 10 is 3628800

Time Complexity: O(n)

Auxiliary Space: O(n)

The above two ways will not work even for small numbers like 20, as its factorial is too big for int to store. Thus we will have an overflow situation on our hands. And if we try to store that number into an int, we will receive a negative output

To solve this, we can store these values in any data structure like an array, ArrayList, linked list, string, etc. In this article, we will be storing this number in an array.

## Using the Carry Over Method

### In Array

As said above, we can’t store the factorial of 20 and above numbers as we will have an overflow condition on our hands. See the image to understand this better.

The simple solution to this problem is to store this number in an array of say size 500.

Using an array of this size will have memory leaks as not all numbers will have this many numbers like the factorial of 20 is 2432902008176640000 and the rest of the memory will be unused leading to a memory leak.

The fix for this solution is to use either an ArrayList or a LinkedList as they are dynamic and will not lead to memory leaks like in the case of arrays.

### Approach

The idea is simple, we just have to go old school for this. Create an array with size 500 as told above with the first element as 1. Now we just to perform some operations like

1. Multiplying this array with x which is initialized as 2
2. Update the array and print it in reverse order

The x in this algorithm denotes the numbers which will be multiplied to get the factorial. Let’s understand the approach

Let’s say we have the array as res, now each element of res[] will be multiplied with x which is 2 which will update the value of res[] inside a loop of x from 2 to the given number.

The important point to note here is digits are multiplied from the rightmost digit to the leftmost digit. If we store digits in the same order in res[], then it becomes difficult to update res[] without extra space. That is why res[] is maintained in a reverse way, i.e., digits from right to left are stored.

### Algorithm

1. Make an array with size 500 with its first element as 1.
2. Loop x from 2 till the given variable where x is the starting value of the factorial eg – 5! = 2*3*4*5
3. Initialize a variable car with 0 which will store our carry-over value.
4. Multiply the elements of res[] with x inside a loop from 0 to the length of res.
5. Update this res[] and car by taking a % and / of the result of this multiplication respectively
6.  Put all digits of the carry-over variable in res[] and increase it by the number of digits in the carry-over variable.

Let’s see the implementation of this algorithm

JAVA
```package com.Tekolio.Extras;

public class Factorial {
public static void main(String[] args) {
int A = 100;
int[] res = fact(A);
for (int re : res) {
System.out.print(re);
}
}

public static int[] fact(int A) {
int[] res = new int;
int len = 1; //present number of digits
res = 1; // adding 1 at 0 index

// traversing from 2 to A
for(int x=2; x<=A; x++) {
int car = 0;
// traversing the array from left to right
for (int i = 0; i < len; i++) {
//multiplying
int fact = res[i] * x + car;
//updating values
res[i] = fact % 10;
car = fact / 10;
}
// if carry is not 0
while (car != 0) {
res[len] = car % 10;
car = car / 10;
len++;
}
}
//reversing the values to get the desired ones
for(int i=0; i<len/2; i++) {
int temp = res[i];
res[i] = res[len-1-i];
res[len-1-i] = temp;
}
return res;
}
}

```
C++
```#include <iostream>
using namespace std;

// Maximum number of digits in output
#define MAX 500

int multiply(int x, int res[], int res_size);

// This function finds factorial of large numbers
// and prints them
void factorial(int n)
{
int res[MAX];

// Initialize result
res = 1;
int res_size = 1;

// Apply simple factorial formula n! = 1 * 2 * 3
// * 4...*n
for (int x = 2; x <= n; x++)
res_size = multiply(x, res, res_size);

cout << "Factorial of given number is \n";
for (int i = res_size - 1; i >= 0; i--)
cout << res[i];
}

// This function multiplies x with the number
// represented by res[].
// res_size is size of res[] or number of digits in the
// number represented by res[]. This function uses simple
// school mathematics for multiplication.
// This function may value of res_size and returns the
// new value of res_size
int multiply(int x, int res[], int res_size)
{
int carry = 0; // Initialize carry

// One by one multiply n with individual digits of res[]
for (int i = 0; i < res_size; i++) {
int prod = res[i] * x + carry;

// Store last digit of 'prod' in res[]
res[i] = prod % 10;

// Put rest in carry
carry = prod / 10;
}

// Put carry in res and increase result size
while (carry) {
res[res_size] = carry % 10;
carry = carry / 10;
res_size++;
}
return res_size;
}

// Driver program
int main()
{
factorial(100);
return 0;
}
```
Python
```import sys

# This function finds factorial of large
# numbers and prints them

def factorial(n):
res = [None]*500
# Initialize result
res = 1
res_size = 1

# Apply simple factorial formula
# n! = 1 * 2 * 3 * 4...*n
x = 2
while x <= n:
res_size = multiply(x, res, res_size)
x = x + 1

print("Factorial of given number is")
i = res_size-1
while i >= 0:
sys.stdout.write(str(res[i]))
sys.stdout.flush()
i = i - 1

# This function multiplies x with the number
# represented by res[]. res_size is size of res[]
# or number of digits in the number represented
# by res[]. This function uses simple school
# mathematics for multiplication. This function
# may value of res_size and returns the new value
# of res_size
def multiply(x, res, res_size):

carry = 0  # Initialize carry

# One by one multiply n with individual
# digits of res[]
i = 0
while i < res_size:
prod = res[i] * x + carry
res[i] = prod % 10  # Store last digit of
# 'prod' in res[]
# make sure floor division is used
carry = prod//10  # Put rest in carry
i = i + 1

# Put carry in res and increase result size
while (carry):
res[res_size] = carry % 10
# make sure floor division is used
# to avoid floating value
carry = carry // 10
res_size = res_size + 1

return res_size

# Driver program
factorial(100)
```

## Output

Factorial of 100 is  933262154439441526816992388562667004907159682643816214685929638952175999932299156089414

Time Complexity: O(N log N!) n for loop and logn! for while loop

Auxiliary Space: O(MAX)

In the above code, we have made an array res[] with a capacity of 500 and made its value at index 0, 1 as while finding any factorial the last digit we have to multiply it with is 1 and it doesn’t change the existing answer. We have also stored the current number of elements which is 1 in a variable len which will also be updated in the later section of the code.

According to the general equation of the factorial, we can also start our multiplication from 2 as 1 multiplied by anything that gives that number only. This is loop is required which will start from 2 and ends at the number given as we did in the above two methods as well.

The thing that makes this approach different from the above two is that in this we will be taking an actual carry variable car which will store our carry-over value and we have to make this 0 every time by adding this value in the answer itself as we did in our school days when we were first understanding multiplication.

And inside the other loop which is for the res[] and starts from 0 till the len variable and contains all the above operations like the multiplication and updating the res and car values for the next iteration.

The answer we will get from this will be in the reversed order, say we are finding the factorial of 5, and the above steps will give an answer like 021. To make it 120 we have to reverse this and we have done this using the temp array method.

## Explanation

Let’s understand the above implementation step by step by finding the factorial of a small number say 5

The first three iterations are simple, we just have to operate the multiplying res[] with x and add carry with it and update both res[] and car as shown below. Process for finding out the factorial of a given large number

The problem arrives when we have a carry-over value which we have encountered in the last step when the value of x is 4.

Now we have to consume this carry in our solution, we will update our res[] until the value of carrying becomes 0 which luckily becomes 0 in just one step. Process for finding out the factorial of a given large number

This process continues until we have received our answer, in this case, it’s 120 in the reverse order. Process for finding out the factorial of a given large number

Now we have to reverse it to get our final output and we can do that very easily using the temp method as shown in the code.

### In Arraylist

The main advantage of using an ArrayList is that we can store the factorial of any number no matter its size as it is dynamic and if the value is small, we dont have to worry about memory leak.

JAVA
```package com.Tekolio.Extras;
import java.util.ArrayList;
public class Factorial {
public static void main(String[] args) {
int A = 100;
ArrayList<Integer> res = new ArrayList<Integer>();
int len = 1; // number of elements
res.add(0,1); // adding element 1 at 0 index

//traversing from 2 to A
for(int x=2; x<=A; x++) {
int car = 0; int fact = 0;

// traversing from right to left
for (int i=len-1; i>=0; i--) {
// multiplication process
fact = res.get(i) * x + car;
//updation process
res.set(i, fact%10);
car = fact / 10;
}
// if carry is not zero
while(car != 0) {
car = car/10;
len++;
}
}
for(int i=0; i<res.size(); i++) {
System.out.print(res.get(i));
}
}
}

```

## Output

Factorial of 100 is  933262154439441526816992388562667004907159682643816214685929638952175999932299156089414

Time Complexity: O(N log N!) –  n for loop  and log N! for while loop

Auxiliary Space: O(n)

## How to Calculate the Factorial of a Big Number?

• Make an array res[] with size MAX, where MAX is the size of the array or the number of maximum digits in output.
• Set the first value or the value of the 0th index of the res[] as 1
• Loop x from 2 till the given variable where x is the starting value of the factorial eg – 5! = 2*3*4*5
• Initialize a variable car with 0 which will store our carry-over value.

## Which number has the largest factorial?

The number 170 is the highest possible number you can calculate a factorial for. Any higher than 170, and the mathematical answer is infinity. Check out this article for more info