Python - Calculate the Factorial of a Large Number Using an Array

Python – Calculate the Factorial of a Large Number Using an Array

When the factorial of a number grows too large to be stored in standard data types, we can use an array to handle each digit of the result. This technique is particularly useful in data structures and algorithms (DSA) interviews, as it demonstrates how to manage big numbers by simulating arithmetic operations manually.

Problem Statement

Given a large integer N, compute N! (the factorial of N) using an array to store each digit of the result. This approach bypasses the limitations of built-in data types when dealing with very large numbers.

Sample Input and Output

Example 1:

</>

Copy

Input: N = 10
Output: 3628800

Example 2:

</>

Copy

Input: N = 25
Output: 15511210043330985984000000

Solution Approach

The steps to calculate the factorial of a large number using an array are as follows:

Initialization: Start with an array containing the number 1 (representing 0! or 1!).
Multiplication: For each number from 2 to N, multiply the current factorial result by that number. Since the result is stored as an array of digits, perform multiplication digit by digit.
Handling Carries: During each multiplication, manage the carry value by updating the subsequent digits in the array.
Final Result: After processing all multiplications, the array will hold the digits of the factorial in reverse order. Reverse the array to obtain the correct sequence and join the digits to form the final number.

Python Program

</>

Copy

# Function to multiply the large number (stored as an array) by an integer x
def multiply(fact, x):
    carry = 0
    for i in range(len(fact)):
        product = fact[i] * x + carry
        fact[i] = product % 10    # Update current digit with remainder
        carry = product // 10     # Calculate carry for next digit
    # Append remaining carry digits to the list
    while carry:
        fact.append(carry % 10)
        carry //= 10
    return fact

# Function to calculate factorial of a large number using an array
def factorial_large(N):
    # Start with an array containing 1 (initial factorial value)
    fact = [1]
    # Multiply fact by each number from 2 to N
    for num in range(2, N + 1):
        fact = multiply(fact, num)
    # Since digits are stored in reverse, reverse the array to get the final result
    fact.reverse()
    # Convert the list of digits into a string
    return ''.join(map(str, fact))

# Sample Test Cases
if __name__ == '__main__':
    # Example 1
    N1 = 10
    print("Factorial of", N1, "is:")
    print(factorial_large(N1))
    
    # Example 2
    N2 = 25
    print("\nFactorial of", N2, "is:")
    print(factorial_large(N2))

Conclusion

This tutorial demonstrated how to calculate the factorial of a large number using an array to store each digit. By initializing with a base value, performing digit-by-digit multiplication while handling carries, and finally reversing the result, we can compute factorials that exceed the capacity of built-in types.

TutorialKart

Python – Calculate the Factorial of a Large Number Using an Array