How Can We Calculate and Display the Factorial of Arbitrarily Large Numbers Without External Libraries?

Factorial Calculation of Arbitrarily Large Numbers with Full Digit Display

Introduction:

In a recent interview, a challenging question arose: calculating the factorial of an arbitrarily large number while simultaneously displaying all its digits. While external libraries like GMP offer convenient solutions, it is essential to explore alternative methods for this task. Here, we present an approach that utilizes an array of integers to represent the factorial without relying on external libraries.

Method:

1. Array Initialization: Create an array of integers, each holding a single digit of the factorial.
2. Factorial Calculation: Iterate over the elements of the array from right to left, multiplying each digit by the given number. Carry any overflow to the next digit.
3. Recursion: Repeat step 2 recursively for each subsequent integer of the factorial, decrementing the input number in each step.
4. Display: Once the factorial has been computed, iterate over the array from left to right, printing each non-zero element (ignoring leading zeros).

Implementation:

#include <iostream>
#include <cstring>

int max = 5000;

// Display all non-zero digits of the array
void display(int arr[]) {
    int ctr = 0;
    for (int i = 0; i < max; i++) {
        if (!ctr && arr[i])         ctr = 1;
        if (ctr)
            std::cout << arr[i];
    }
}

// Calculate the factorial of 'n' and store it in 'arr'
void factorial(int arr[], int n) {
    if (!n) return;
    int carry = 0;
    for (int i = max - 1; i >= 0; --i) {
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i] / 10;
        arr[i] %= 10;
    }
    factorial(arr, n - 1);
}

int main() {
    int *arr = new int[max];
    std::memset(arr, 0, max * sizeof(int));
    arr[max - 1] = 1;
    int num;
    std::cout << "Enter the number: ";
    std::cin >> num;
    std::cout << "Factorial of " << num << " is :\n";
    factorial(arr, num);
    display(arr);
    delete[] arr;
    return 0;
}

Explanation:

This code uses an integer array 'arr' to represent the factorial. The function 'factorial' recursively calculates the factorial and stores it in 'arr'. The function 'display' prints the non-zero digits of 'arr', ensuring the readability of the factorial.

Conclusion:

The presented approach demonstrates a method for calculating the factorial of arbitrarily large numbers without using external libraries. It utilizes an array-based representation to capture all the digits of the factorial and display them in their full glory. This method not only fulfills the interview requirement but also underscores the importance of understanding the underlying principles of number manipulation in programming.

The above is the detailed content of How Can We Calculate and Display the Factorial of Arbitrarily Large Numbers Without External Libraries?. For more information, please follow other related articles on the PHP Chinese website!