Factorial Of Large Number

Posted: 1 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Given an integer ‘N’, you are supposed to return the factorial of the given integer in the form of a string.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases.

Each test case contains a single line with a single integer ‘N’ denoting the given number.

Output format :

For each test case, print a string denoting the factorial of the given number in a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 500

Time Limit: 1 sec.
Approach 1

Since the factorials of large integers exceed 10^18 they cannot be stored in any variable of primitive data type, hence the idea is to use an array to store the factorial of the numbers.

 

Steps are as follows:

 

  1. In order to store the factorial of a number, we create a “result” array/list in which at each index we will store exactly one digit.  To calculate the factorial of ‘N’ we need to multiply all numbers from 1 to N which means we need to run a loop from 2 to ‘N’ and multiply each integer.
  2. Let’s define a helper function to multiply an integer ‘X’ with the number represented by the “result” array. This function uses simple calculations to perform the multiplication.
    1. Firstly initialise a variable “carryOver” as 0.
    2. For all the digits in the result array do the following step.
      1. Let's say we are at the i'th digit of the multiplicand.
        1. value = result[i]*x+carryOver.
        2. result[i] = product mod 10.
        3. carryOver = product / 10.
    3. Here, what we were doing is we one by one multiplying ‘X’ with every digit of “result”. The multiplication is done from the rightmost digit to the leftmost digit. If we store digits in the same order in “result”, then it becomes difficult to update the "result" array without extra space. Hence, “result” is maintained in the reverse way, i.e., digits from right to left are stored.
    4. Now run a loop until “carryOver” is not equal to 0.
    5. Insert (carryOver % 10) at the end of the multiplicand array and in each iteration update carryOver = carryOver / 10.
Try Problem