# Calculate factorial of large number

The problem deals with calculating the factorial of a large number. The factorial of a non-negative integer 'n' is the product of all positive integers from 1 to 'n'. Factorials can grow extremely large, making direct multiplication and storage impractical for larger values of 'n'. Thus, efficient algorithms are required to compute the factorial of large numbers.

## Problem Statement

Given a non-negative integer 'n', the goal is to calculate and display its factorial, which is the product of all positive integers from 1 to 'n'.

## Example

Let's consider an example to better understand the problem:

• Given 'n' = 25
• We need to find the factorial of 25.

## Idea to Solve

1. We need to handle large numbers, so using standard integer or long data types won't suffice.
2. We'll utilize an array (or vector in this case) to store digits of the factorial.
3. Starting with the initial value of 1, we'll iterate from 2 to 'n' and continuously multiply the array with the current value.
4. To perform multiplication, we'll simulate the manual multiplication process where we keep track of carry.
5. We'll multiply each digit of the array with the current value and handle the carry and digits accordingly.

## Pseudocode

``````function multiply(array, value):
carry = 0
for i from 0 to array.size() - 1:
product = array[i] * value + carry
array[i] = product % 10
carry = product / 10
while carry > 0:
carry = carry / 10

function calculateFactorial(n):
array = 
for value from 2 to n:
multiply(array, value)
reverse the array
return array

# Example usage
n = 25
factorialArray = calculateFactorial(n)
for digit in factorialArray:
print(digit, end="")``````

## Algorithm Explanation

1. The `multiply` function performs digit-wise multiplication of an array with a value while handling carry.
2. The `calculateFactorial` function initializes an array with a value of 1.
3. It then iterates from 2 to 'n', calling the `multiply` function to update the array.
4. After all multiplications, the array is reversed to get the correct order of digits.
5. The digits of the factorial are printed in the correct order.

## Code Solution

``````import java.util.Vector;
/*
Java program
Calculate factorial of large number
*/
public class Factorial
{
public void multiply(Vector < Integer > record, int v)
{
int carry = 0;
int product = 0;
for (int i = 0; i < record.size(); ++i)
{
product = record.get(i) * v + carry;
// Update value
record.set(i, product % 10);
carry = product / 10;
}
// When carry not zero
while (carry > 0)
{
// Remove last digit in carry
carry = carry / 10;
}
}
public void findFactorial(int n)
{
if (n < 0)
{
return;
}
Vector < Integer > record = new Vector < Integer > ();
// First element
for (int v = 2; v <= n; ++v)
{
multiply(record, v);
}
// Display calculated value
for (int i = record.size() - 1; i >= 0; --i)
{
System.out.print(record.get(i));
}
}
public static void main(String[] args)
{
}
}``````

#### Output

``15511210043330985984000000``
``````// Include header file
#include <iostream>
#include <vector>

using namespace std;
/*
C++ program
Calculate factorial of large number
*/
class Factorial
{
public: void multiply(vector < int > &record, int v)
{
int carry = 0;
int product = 0;
for (int i = 0; i < record.size(); ++i)
{
product = record.at(i) * v + carry;
// Update value
record.at(i) = product % 10;
carry = product / 10;
}
// When carry not zero
while (carry > 0)
{
record.push_back(carry % 10);
// Remove last digit in carry
carry = carry / 10;
}
}
void findFactorial(int n)
{
if (n < 0)
{
return;
}
vector < int > record;
// First element
record.push_back(1);
for (int v = 2; v <= n; ++v)
{
this->multiply(record, v);
}
// Display calculated value
for (int i = record.size() - 1; i >= 0; --i)
{
cout << record.at(i);
}
}
};
int main()
{
return 0;
}``````

#### Output

``15511210043330985984000000``
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program
Calculate factorial of large number
*/
public class Factorial
{
public void multiply(List < int > record, int v)
{
int carry = 0;
int product = 0;
for (int i = 0; i < record.Count; ++i)
{
product = record[i] * v + carry;
// Update value
record[i] = product % 10;
carry = product / 10;
}
// When carry not zero
while (carry > 0)
{
// Remove last digit in carry
carry = carry / 10;
}
}
public void findFactorial(int n)
{
if (n < 0)
{
return;
}
List < int > record = new List < int > ();
// First element
for (int v = 2; v <= n; ++v)
{
this.multiply(record, v);
}
// Display calculated value
for (int i = record.Count - 1; i >= 0; --i)
{
Console.Write(record[i]);
}
}
public static void Main(String[] args)
{
}
}``````

#### Output

``15511210043330985984000000``
``````package main
import "fmt"
/*
Go program
Calculate factorial of large number
*/
type Factorial struct {}
func getFactorial() * Factorial {
var me *Factorial = &Factorial {}
return me
}
func(this Factorial) multiply(record*[]int, v int) {
var carry int = 0
var product int = 0
for i := 0 ; i < len(*record) ; i++ {
product = ((*record)[i]) * v + carry
// Update value
(*record)[i] = product % 10
carry = product / 10
}
// When carry not zero
for (carry > 0) {
(*record) = append((*record), carry % 10)
// Remove last digit in carry
carry = carry / 10
}
}
func(this Factorial) findFactorial(n int) {
if n < 0 {
return
}
var record = make([]int,0)
// First element
record = append(record, 1)
for v := 2 ; v <= n ; v++ {
this.multiply(&record, v)
}
// Display calculated value
for i := len(record) - 1 ; i >= 0 ; i-- {
fmt.Print(record[i])
}
}
func main() {
var task * Factorial = getFactorial()
}``````

#### Output

``15511210043330985984000000``
``````<?php
/*
Php program
Calculate factorial of large number
*/
class Factorial
{
public	function multiply(&\$record, \$v)
{
\$carry = 0;
\$product = 0;
for (\$i = 0; \$i < count(\$record); ++\$i)
{
\$product = \$record[\$i] * \$v + \$carry;
// Update value
\$record[\$i] = \$product % 10;
\$carry = (int)(\$product / 10);
}
// When carry not zero
while (\$carry > 0)
{
\$record[] = \$carry % 10;
// Remove last digit in carry
\$carry = (int)(\$carry / 10);
}
}
public	function findFactorial(\$n)
{
if (\$n < 0)
{
return;
}
\$record = array();
// First element
\$record[] = 1;
for (\$v = 2; \$v <= \$n; ++\$v)
{
\$this->multiply(\$record, \$v);
}
// Display calculated value
for (\$i = count(\$record) - 1; \$i >= 0; --\$i)
{
echo(\$record[\$i]);
}
}
}

function main()
{
}
main();``````

#### Output

``15511210043330985984000000``
``````/*
Node JS program
Calculate factorial of large number
*/
class Factorial
{
multiply(record, v)
{
var carry = 0;
var product = 0;
for (var i = 0; i < record.length; ++i)
{
product = record[i] * v + carry;
// Update value
record[i] = product % 10;
carry = parseInt(product / 10);
}
// When carry not zero
while (carry > 0)
{
record.push(carry % 10);
// Remove last digit in carry
carry = parseInt(carry / 10);
}
}
findFactorial(n)
{
if (n < 0)
{
return;
}
var record = [];
// First element
record.push(1);
for (var v = 2; v <= n; ++v)
{
this.multiply(record, v);
}
// Display calculated value
for (var i = record.length - 1; i >= 0; --i)
{
process.stdout.write(""+record[i]);
}
}
}

function main()
{
}
main();``````

#### Output

``15511210043330985984000000``
``````#    Python 3 program
#    Calculate factorial of large number
class Factorial :
def multiply(self, record, v) :
carry = 0
product = 0
i = 0
while (i < len(record)) :
product = record[i] * v + carry
#  Update value
record[i] = product % 10
carry = int(product / 10)
i += 1

#  When carry not zero
while (carry > 0) :
record.append(carry % 10)
#  Remove last digit in carry
carry = int(carry / 10)

def findFactorial(self, n) :
if (n < 0) :
return

record = []
#  First element
record.append(1)
v = 2
while (v <= n) :
self.multiply(record, v)
v += 1

i = len(record) - 1
#  Display calculated value
while (i >= 0) :
print(record[i], end = "")
i -= 1

def main() :

if __name__ == "__main__": main()``````

#### Output

``15511210043330985984000000``
``````#    Ruby program
#    Calculate factorial of large number
class Factorial
def multiply(record, v)
carry = 0
product = 0
i = 0
while (i < record.length)
product = record[i] * v + carry
#  Update value
record[i] = product % 10
carry = product / 10
i += 1
end

#  When carry not zero
while (carry > 0)
record.push(carry % 10)
#  Remove last digit in carry
carry = carry / 10
end

end

def findFactorial(n)
if (n < 0)
return
end

record = []
#  First element
record.push(1)
v = 2
while (v <= n)
self.multiply(record, v)
v += 1
end

i = record.length - 1
#  Display calculated value
while (i >= 0)
print(record[i])
i -= 1
end

end

end

def main()
end

main()``````

#### Output

``15511210043330985984000000``
``````import scala.collection.mutable._;
/*
Scala program
Calculate factorial of large number
*/
class Factorial()
{
def multiply(record: ArrayBuffer[Int], v: Int): Unit = {
var carry: Int = 0;
var product: Int = 0;
var i: Int = 0;
while (i < record.size)
{
product = record(i) * v + carry;
// Update value
record(i) = (product % 10);
carry = product / 10;
i += 1;
}
// When carry not zero
while (carry > 0)
{
record += carry % 10;
// Remove last digit in carry
carry = carry / 10;
}
}
def findFactorial(n: Int): Unit = {
if (n < 0)
{
return;
}
var record: ArrayBuffer[Int] = new ArrayBuffer[Int]();
// First element
record += 1;
var v: Int = 2;
while (v <= n)
{
multiply(record, v);
v += 1;
}
var i: Int = record.size - 1;
// Display calculated value
while (i >= 0)
{
print(record(i));
i -= 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Factorial = new Factorial();
}
}``````

#### Output

``15511210043330985984000000``
``````import Foundation;
/*
Swift 4 program
Calculate factorial of large number
*/
class Factorial
{
func multiply(_ record: inout[Int], _ v: Int)
{
var carry: Int = 0;
var product: Int = 0;
var i: Int = 0;
while (i < record.count)
{
product = record[i] * v + carry;
// Update value
record[i] = product % 10;
carry = product / 10;
i += 1;
}
// When carry not zero
while (carry > 0)
{
record.append(carry % 10);
// Remove last digit in carry
carry = carry / 10;
}
}
func findFactorial(_ n: Int)
{
if (n < 0)
{
return;
}
var record: [Int] = [Int]();
// First element
record.append(1);
var v: Int = 2;
while (v <= n)
{
self.multiply(&record, v);
v += 1;
}
var i: Int = record.count - 1;
// Display calculated value
while (i >= 0)
{
print(record[i], terminator: "");
i -= 1;
}
}
}
func main()
{
}
main();``````

#### Output

``15511210043330985984000000``
``````/*
Kotlin program
Calculate factorial of large number
*/
class Factorial
{
fun multiply(record: MutableList < Int > , v : Int): Unit
{
var carry: Int = 0;
var product: Int ;
var i: Int = 0;
while (i < record.size)
{
product = record[i] * v + carry;
// Update value
record.set(i,product % 10);
carry = product / 10;
i += 1;
}
// When carry not zero
while (carry > 0)
{
// Remove last digit in carry
carry = carry / 10;
}
}
fun findFactorial(n: Int): Unit
{
if (n < 0)
{
return;
}
val record: MutableList < Int > = mutableListOf < Int > ();
// First element
var v: Int = 2;
while (v <= n)
{
this.multiply(record, v);
v += 1;
}
var i: Int = record.size - 1;
// Display calculated value
while (i >= 0)
{
print(record[i]);
i -= 1;
}
}
}
fun main(args: Array < String > ): Unit
{
}``````

#### Output

``15511210043330985984000000``

## Time Complexity

• The outer loop iterates 'n - 1' times.
• The inner multiplication operation takes O(d), where 'd' is the number of digits in the result.
• Overall, the time complexity is O(n * d), where 'n' is the given number and 'd' is the number of digits in the factorial.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.