Skip to main content

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:
        array.add(carry % 10)
        carry = carry / 10

function calculateFactorial(n):
    array = [1]
    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)
		{
			// Add new record element
			record.add(carry % 10);
			// 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
		record.add(1);
		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)
	{
		Factorial task = new Factorial();
		task.findFactorial(25);
	}
}

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)
		{
			// Add new record element
			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()
{
	Factorial *task = new Factorial();
	task->findFactorial(25);
	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)
		{
			// Add new record element
			record.Add(carry % 10);
			// 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
		record.Add(1);
		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)
	{
		Factorial task = new Factorial();
		task.findFactorial(25);
	}
}

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) {
		// Add new record element
		(*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()
	task.findFactorial(25)
}

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)
		{
			// Add new record element
			$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()
{
	$task = new Factorial();
	$task->findFactorial(25);
}
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)
		{
			// Add new record element
			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()
{
	var task = new Factorial();
	task.findFactorial(25);
}
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) :
			#  Add new record element
			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() :
	task = Factorial()
	task.findFactorial(25)

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) 
			#  Add new record element
			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() 
	task = Factorial.new()
	task.findFactorial(25)
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)
		{
			// Add new record element
			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();
		task.findFactorial(25);
	}
}

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)
		{
			// Add new record element
			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()
{
	let task: Factorial = Factorial();
	task.findFactorial(25);
}
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)
		{
			// Add new record element
			record.add(carry % 10);
			// 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
		record.add(1);
		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
{
	val task: Factorial = Factorial();
	task.findFactorial(25);
}

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.
Last updated on by Kalkicode




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.

New Comment