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.

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;
   }
}

#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;
}

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))

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.

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);
    }
}

#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;
}

def factorial(n):
      
    if n == 0:
        return 1
     
    return n * factorial(n-1)
  
# Driver Code
num = 10;
print("Factorial of", num, "is",
factorial(num))

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

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[500];
       int len = 1; //present number of digits
       res[0] = 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;
   }
}

#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[0] = 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;
}

import sys
 
# This function finds factorial of large
# numbers and prints them
 
 
def factorial(n):
    res = [None]*500
    # Initialize result
    res[0] = 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)

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.

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.

This process continues until we have received our answer, in this case, it’s 120 in the reverse order.

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.

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) {
                res.add(0, car%10);
                car = car/10;
                len++;
            }
        }
        for(int i=0; i<res.size(); i++) {
            System.out.print(res.get(i));
        }
    }
}

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

Auxiliary Space: O(n)

Frequently Asked Questions