Factorial of a Number

Moderate
0/80
Average time to solve is 25m
69 upvotes
Asked in companies
HCL TechnologiesWells FargoSquadstack

Problem statement

You are given an integer ‘N’. You have to print the value of Factorial of ‘N’. The Factorial of a number ‘N’ is defined as the product of all numbers from 1 to ‘N’.

For Example: 
Consider if ‘N’ = 4, the Factorial of 4 will be the product of all numbers from 1 to 4, which is 1 * 2 * 3 * 4 = 24. Hence, the answer is 24.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first and only line of each test case contains one single integer ‘N’ representing the given integer.
Output Format: 
For each test case, print the value of factorial of ‘N’.

Print the output of each test case in a separate line.
Constraints: 
1 <= T <= 10
1 <= N <= 100

Time limit: 1 sec
Sample Input 1:
2
4
3
Sample Output 1:
24
6
Explanation of sample input 1:
For the first test case, 
The Factorial of 4 is the product of all numbers from 1 to 4, which is 1 * 2 * 3 * 4 = 24. Hence, the answer is 24.

For the second test case,
The Factorial of 3 is the product of all numbers from 1 to 3, which is 1 * 2 * 3 = 6. Hence, the answer is 6.
Sample Input 2:
2
8
11
Sample Output 2:
40320
39916800
Hint

Can you find any method to use a linked list in the problem?

Approaches (2)
Using Linked List

In this approach, we will calculate the factorial of the given number and store it in the form of a Linked List of digits named digits. To do this, we will define a function multiply(digits,x) that will multiply the number corresponding to the digits with x and update the digits with the product’s value. Then we will initialize the linked list digits with 1 and multiply it with all numbers from 2 to N using the multiply function. At last, we will print the list in reverse order.

 

Algorithm:

  • Defining the Node structure of the linked list:
    • The class Node will have two variables, val to store the value and next pointer to store the address of the next element.

 

  • Defining multiply(digits,x) function:
    • digits represent the head node of the linked list, and x is the number to be multiplied.
    • Declare a variable carry to store carry value and initialize it with 0.
    • We will iterate over all the nodes of the digits and update their values.
    • Initialize a node temp as digits.
    • While temp is not empty, do the following:
      • The product prod will the (val of temp * x)  + carry.
      • Set val of node as prod%10.(Last digit of the prod).
      • Update carry as prod/10. (Value after removing the last digit).
      • Set temp as next of temp.
    • If we still have any carry value left, we have to include some extra digits at the end of the Linked List.
    • While carry is not zero, do the following steps:
      • Insert a new node with val as carry%10 (last digit of carry) to the end of digits.
      • Set carry as carry/10 (The last digit of carry is removed).

 

  • We will declare linked list digits to store the digits of the factorial value.
  • Create a node digits with val as 1.
  • For each number num from 2 to N, do the following steps:
    • Update the values of digits by calling multiply(digits, num).
  • Print the linked list digits in reverse order.
Time Complexity

O(N), where N is the given number.

 

We are calling multiply function N times, and in each iteration, we are iterating over the whole digits list, which will take constant time. Hence, the overall time complexity is O(N).

Space Complexity

O(1).
 

In this approach, we used a linked list to store the digits of the factorial value. In the worst case, the digits linked list contains at most 200 elements. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Factorial of a Number
Full screen
Console