Mathematical Answer For 31 Factorial

Factorial of a non-negative integer, is the multiplication of all integers smaller than or equal to n. For example factorial of 6 is 6*5*4*3*2*1 which is 720.

factorial

Attention reader! Don't stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course .

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

We have discussed simple program for factorial.

How to compute factorial of 100 using a C/C++ program?
Factorial of 100 has 158 digits. It is not possible to store these many digits even if we use long long int.

Examples :

Input : 100 Output : 933262154439441526816992388562667004-          907159682643816214685929638952175999-          932299156089414639761565182862536979-          208272237582511852109168640000000000-          00000000000000  Input :50 Output : 3041409320171337804361260816606476884-          4377641568960512000000000000

Following is a simple solution where we use an array to store individual digits of the result. The idea is to use basic mathematics for multiplication.

The following is a detailed algorithm for finding factorial.
factorial(n)
1) Create an array 'res[]' of MAX size where MAX is number of maximum digits in output.
2) Initialize value stored in 'res[]' as 1 and initialize 'res_size' (size of 'res[]') as 1.
3) Do following for all numbers from x = 2 to n.
……a) Multiply x with res[] and update res[] and res_size to store the multiplication result.

How to multiply a number 'x' with the number stored in res[]?
The idea is to use simple school mathematics. We one by one multiply x with every digit of res[]. The important point to note here is digits are multiplied from rightmost digit to leftmost digit. If we store digits in same order in res[], then it becomes difficult to update res[] without extra space. That is why res[] is maintained in reverse way, i.e., digits from right to left are stored.

multiply(res[], x)
1) Initialize carry as 0.
2) Do following for i = 0 to res_size – 1
….a) Find value of res[i] * x + carry. Let this value be prod.
….b) Update res[i] by storing last digit of prod in it.
….c) Update carry by storing remaining digits in carry.
3) Put all digits of carry in res[] and increase res_size by number of digits in carry.

          Example to show working of multiply(res[], x)          A number 5189 is stored in res[] as following. res[] = {9, 8, 1, 5} x = 10  Initialize carry = 0;  i = 0, prod = res[0]*x + carry = 9*10 + 0 = 90. res[0] = 0, carry = 9  i = 1, prod = res[1]*x + carry = 8*10 + 9 = 89 res[1] = 9, carry = 8  i = 2, prod = res[2]*x + carry = 1*10 + 8 = 18 res[2] = 8, carry = 1  i = 3, prod = res[3]*x + carry = 5*10 + 1 = 51 res[3] = 1, carry = 5  res[4] = carry = 5  res[] = {0, 9, 8, 1, 5}

Below is the implementation of the above algorithm.

NOTE : In the below implementation, maximum digits in the output are assumed as 500. To find a factorial of a much larger number ( > 254), increase the size of an array or increase the value of MAX.

C++

#include<iostream>

using namespace std;

#define MAX 500

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

void factorial( int n)

{

int res[MAX];

res[0] = 1;

int res_size = 1;

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

}

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

{

int carry = 0;

for ( int i=0; i<res_size; i++)

{

int prod = res[i] * x + carry;

res[i] = prod % 10;

carry = prod/10;

}

while (carry)

{

res[res_size] = carry%10;

carry = carry/10;

res_size++;

}

return res_size;

}

int main()

{

factorial(100);

return 0;

}

Java

class GFG {

static void factorial( int n)

{

int res[] = new int [ 500 ];

res[ 0 ] = 1 ;

int res_size = 1 ;

for ( int x = 2 ; x <= n; x++)

res_size = multiply(x, res, res_size);

System.out.println( "Factorial of given number is " );

for ( int i = res_size - 1 ; i >= 0 ; i--)

System.out.print(res[i]);

}

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

{

int carry = 0 ;

for ( int i = 0 ; i < res_size; i++)

{

int prod = res[i] * x + carry;

res[i] = prod % 10 ;

carry = prod/ 10 ;

}

while (carry!= 0 )

{

res[res_size] = carry % 10 ;

carry = carry / 10 ;

res_size++;

}

return res_size;

}

public static void main(String args[])

{

factorial( 100 );

}

Python

import sys

def factorial( n) :

res = [ None ] * 500

res[ 0 ] = 1

res_size = 1

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

def multiply(x, res,res_size) :

carry = 0

i = 0

while i < res_size :

prod = res[i] * x + carry

res[i] = prod % 10 ;

carry = prod / / 10 ;

i = i + 1

while (carry) :

res[res_size] = carry % 10

carry = carry / / 10

res_size = res_size + 1

return res_size

factorial( 100 )

C#

using System;

class GFG

{

static void factorial( int n)

{

int []res = new int [500];

res[0] = 1;

int res_size = 1;

for ( int x = 2; x <= n; x++)

res_size = multiply(x, res,

res_size);

Console.WriteLine( "Factorial of " +

"given number is " );

for ( int i = res_size - 1; i >= 0; i--)

Console.Write(res[i]);

}

static int multiply( int x, int []res,

int res_size)

{

int carry = 0;

for ( int i = 0; i < res_size; i++)

{

int prod = res[i] * x + carry;

res[i] = prod % 10;

carry = prod / 10;

}

while (carry != 0)

{

res[res_size] = carry % 10;

carry = carry / 10;

res_size++;

}

return res_size;

}

static public void Main ()

{

factorial(100);

}

PHP

<?php

$MAX = 500;

function factorial( $n )

{

global $MAX ;

$res = array_fill (0, $MAX , 0);

$res [0] = 1;

$res_size = 1;

for ( $x = 2; $x <= $n ; $x ++)

$res_size = multiply( $x , $res , $res_size );

echo "Factorial of given number is \n" ;

for ( $i = $res_size - 1; $i >= 0; $i --)

echo $res [ $i ];

}

function multiply( $x , & $res , $res_size )

{

$carry = 0;

for ( $i = 0; $i < $res_size ; $i ++)

{

$prod = $res [ $i ] * $x + $carry ;

$res [ $i ] = $prod % 10;

$carry = (int)( $prod / 10);

}

while ( $carry )

{

$res [ $res_size ] = $carry % 10;

$carry = (int)( $carry / 10);

$res_size ++;

}

return $res_size ;

}

factorial(100);

?>

Javascript

<script>

function factorial(n)

{

let res = new Array(500);

res[0] = 1;

let res_size = 1;

for (let x=2; x<=n; x++)

res_size = multiply(x, res, res_size);

document.write( "Factorial of given number is " + "<br>" );

for (let i=res_size-1; i>=0; i--)

document.write(res[i]);

}

function multiply(x, res, res_size)

{

let carry = 0;

for (let i=0; i<res_size; i++)

{

let prod = res[i] * x + carry;

res[i] = prod % 10;

carry = Math.floor(prod/10);

}

while (carry)

{

res[res_size] = carry%10;

carry = Math.floor(carry/10);

res_size++;

}

return res_size;

}

factorial(100);

</script>

Output

Factorial of given number is  93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

The above approach can be optimized in many ways. We will soon be discussing an optimized solution for the same.
This article is contributed by Harshit Agrawal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

Program 2: (BigInteger method)

Big Integer can also be used to calculate factorial of large numbers.

Java

import java.math.BigInteger;

import java.util.Scanner;

public class Example {

static BigInteger factorial( int N)

{

BigInteger f

= new BigInteger( "1" );

for ( int i = 2 ; i <= N; i++)

f = f.multiply(BigInteger.valueOf(i));

return f;

}

public static void main(String args[]) throws Exception

{

int N = 20 ;

System.out.println(factorial(N));

}

Output

2432902008176640000

Program 3: (Using LinkedList)

Linked List can also be used, this approach will not waste any extra space.

C++

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i <= b; i++)

using namespace std;

class Node {

public :

int data;

Node* prev;

Node( int n)

{

data = n;

prev = NULL;

}

};

void Multiply(Node* tail, int n)

{

Node *temp = tail,

*prevNode = tail;

int carry = 0;

while (temp != NULL) {

int data = temp->data * n + carry;

temp->data = data % 10;

carry = data / 10;

prevNode = temp;

temp = temp->prev;

}

while (carry != 0) {

prevNode->prev = new Node(( int )(carry % 10));

carry /= 10;

prevNode = prevNode->prev;

}

void print(Node* tail)

{

if (tail == NULL)

return ;

print(tail->prev);

cout

<< tail->data;

}

int main()

{

int n = 20;

Node tail(1);

rep(i, 2, n)

Multiply(&tail, i);

print(&tail);

cout << endl;

return 0;

}

Output

2432902008176640000