Factorial Of Large Number

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
77 upvotes
Asked in companies
AdobeMakeMyTripMicrosoft

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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.
Sample Input 1:
2
3
4
Sample Output 1:
6
24
Explanation to Sample Input 1:
In the first test case, the factorial of 3 is 1x2x3 = 6.

In the second test case, the factorial of 4 is 1x2x3x4 = 24.
Sample Input 2:
2
5
1
Sample Output 2:
120
1
Hint

Think about a data structure to store the factorials for large integers.

Approaches (1)
Factorial Calculation

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.
Time Complexity

O(N*M), where ‘N’ is the given integer and ‘M’ is the size of the result array.

 

Since we are going through ‘N’ iterations and in the helper function it takes ‘M’ iterations so the overall time complexity will be O(N*M).

Space Complexity

O(M), where ‘M’ is the size of the result array.

 

To store the result ‘M’ space is required, so the overall space complexity will be O(M).

Code Solution
(100% EXP penalty)
Factorial Of Large Number
Full screen
Console