Find Factorial of a Number.
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.

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

Question

Find Factorial of a Number.

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.

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

Accepted Answer

Factorial can be calculated using following recursive formula :

n! = n * (n-1)!

n! = 1 if n = 0 or n = 1

Factorial can also be calculated iteratively as recursion can be costly for large numbers.

Factorial(n)
{
	Initialize a variable res = 1
	for (i = 2 to i <= n) do :
	res = res* i
	return res
}

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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).

Time Complexity: O(n)Explanation:

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).

Java (SE 1.8)

/*
	Time Complexity: O(N)
	Space Complexity: O(1)
	
	Where N is the given number.
*/

//The node class to defining the structure of node
class Node {
	int val;
	Node next;

	Node() {
	}

	Node(int val) {
		this.val = val;
	}
};

public class Solution {

	// Multiply function will multiply the number formed by digits list with x
	public static void multiply(Node digits, int x) {

		// The variable temp to traverse through the list
		Node temp = digits;

		Node last = new Node();

		// Initialize carry as 0
		int carry = 0;

		// Traversing the digits linked list.
		while (temp != null) {

			// The prod will store the product of temp's val and x.
			int prod = temp.val * x + carry;

			temp.val = prod % 10;
			carry = prod / 10;

			// Storing the last node of the digits
			if (temp.next == null) {
				last = temp;
			}

			temp = temp.next;
		}

		// Iterate till carry is not equal to 0
		while (carry != 0) {
			last.next = new Node(carry % 10);
			carry = carry / 10;
			last = last.next;
		}
	}

	// A recursive function to print the list in reverse order.
	static void printReverse(Node cur) {
		if (cur == null) {
			return;
		}

		printReverse(cur.next);

		System.out.print(cur.val);
	}

	public static void factorial(int n) {

		// Declaring the digits list with val as 1
		Node digits = new Node(1);

		// Multiplying digits list with all numbers from 2 to n.
		for (int num = 2; num < n + 1; num++) {
			multiply(digits, num);
		}

		// Printing the list in the reverse order.
		printReverse(digits);
	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the given number.

*/



// The node class to defining the structure of node

class Node

{

    public: 

    int val;

    Node* next; 



    Node(int val)

    {

        next = NULL;

        this->val = val;

    }

};



// Multiply function will multiply the number formed by digits list with x

void multiply(Node *digits, int x)

{

    // The variable temp to traverse through the list

    Node *temp = digits;

	

    Node* last;

    

    // Initialize carry as 0

    int carry = 0;



    // Traversing the digits linked list.

    while(temp != NULL)

    {

        // The prod will store the product of temp's val and x.

        int prod = temp->val * x + carry;



        temp->val = prod % 10;

        carry = prod / 10;



        // Storing the last node of the digits

        if(temp->next == NULL)

        {

            last = temp;

        }



        temp = temp->next;

    }



    // Iterate till carry is not equal to 0

    while(carry != 0)

    {

        last->next = new Node(carry % 10);

        carry = carry / 10;

        last = last->next;

    }

}





// A recursive function to print the list in reverse order.

void printReverse(Node *cur)

{

    if(cur == NULL)

    {

        return;

    }



    printReverse(cur->next);



    cout<val;

}



void factorial(int n)

{

    // Declaring the digits list with val as 1

    Node *digits = new Node(1);



    // Multiplying digits list with all numbers from 2 to n.

    for(int num = 2; num < n + 1; num++)

    {

        multiply(digits, num);

    }



    // Printing the list in the reverse order.

    printReverse(digits);

}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the given number.

"""



# The node class to defining the structure of node

class Node:

    def __init__(self, val):

        self.next = None

        self.val = val





# Multiply function will multiply the number formed by digits list with x

def multiply(digits, x):



    # The variable temp to traverse through the list

    temp = digits



    # Initialize carry as 0

    carry = 0



    # Traversing the digits linked list.

    while(temp != None):



        # The prod will store the product of temp's val and x.

        prod = temp.val * x + carry



        temp.val = prod % 10

        carry = prod // 10



        # Storing the last node of the digits

        if(temp.next == None):

            last = temp



        temp = temp.next



    # Iterate till carry is not equal to 0

    while(carry != 0):

        last.next = Node(carry % 10)

        carry = carry // 10

        last = last.next





# A recursive function to print the list in reverse order.

def printReverse(cur):



    if(cur == None):

        return



    printReverse(cur.next)



    print(cur.val, end="")





def factorial(n):



    # Declaring the digits list with val as 1

    digits =Node(1)



    # Multiplying digits list with all numbers from 2 to n.

    for num in range(2, n + 1):

        multiply(digits, num)



    # Printing the list in the reverse order.

    printReverse(digits)

Accepted Answer

Using An Array

In this approach, we will calculate the factorial of the given number and store it in the form of an array of digits named digits. To do this, we will define a function multiply(digits, x) that will multiply the number corresponding to the digits array with x and update the digits array with the product’s value.

We will initialize the digits array with 1 and multiply it with all numbers from 2 to N using the multiply function. At last, we will print the digits array.

Algorithm:

Defining multiply(digits,x) function:
- Declare a variable carry to store carry value and initialize it with 0.
- We will iterate over all the numbers of the digits array and update its values.
- For each index idx from 0 to length of digits -1, do the following:
  - The product prod will the (digits[idx] * x) + carry.
  - Set digits[idx] as prod%10.(Last digit of the prod)
  - Update carry as prod/10. (Value after removing the last digit)
- If we still have any carry value left, we have to include some extra digits at the end of the digits array.
- While carry is not zero, do the following steps:
  - Insert carry%10 (last digit of carry) to the end of digits.
  - Set carry as carry/10 (The last digit of carry is deleted).

We will declare an array digits to store the digits of the factorial value.
Insert 1 into the array digits.
For each number num from 2 to N, do the following steps:
- Update the values of digits by calling multiply(digits, num).
Print the elements of digits array in the reverse order.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n)Explanation:

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 array, which will take constant time. Hence, the overall time complexity is O(N).

Java (SE 1.8)


/*
	Time Complexity: O(N)
	Space Complexity: O(1)
	
	Where N is the given number.
*/

import java.util.ArrayList;

public class Solution {
	public static void multiply(ArrayList digits, int x) {

		// Initialize carry as zero.
		int carry = 0;

		// Traversing the whole digits array and updating its values.
		for (int idx = 0; idx < digits.size(); idx++) {
			int prod = x * digits.get(idx) + carry;
			digits.set(idx, prod % 10);
			carry = prod / 10;
		}

		// Iterate till carry is not equal to 0
		while (carry != 0) {
			digits.add(carry % 10);
			carry = carry / 10;
		}
	}

	public static void factorial(int n) {

		// Declaring digits arrayList and inserting 1 into digits.
		ArrayList digits = new ArrayList();
		digits.add(1);

		// Multiplying digits array with all numbers from 2 to n.
		for (int num = 2; num < n + 1; num++) {
			multiply(digits, num);
		}

		// Printing the array in the reverse order.
		for (int i = digits.size() - 1; i >= 0; i--) {
			System.out.print(digits.get(i));
		}
	}
}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the given number.

*/



void multiply(vector &digits, int x)

{

    // Initialize carry as zero.

    int carry = 0;



    // Traversing the whole digits array and updating its values.

    for(int idx = 0; idx < digits.size(); idx++)

    {

        int prod = x * digits[idx] + carry;

        digits[idx] = prod % 10;

        carry = prod / 10;

    }



    // Iterate till carry is not equal to 0

    while(carry != 0)

    {

        digits.push_back(carry % 10);

        carry = carry / 10;

    }

}



void factorial(int n)

{

    // Declaring digits array and inserting 1 into digits.

    vector digits;

    digits.push_back(1);

    

    // Multiplying digits array with all numbers from 2 to n.

    for(int num = 2; num < n + 1; num++)

    {

        multiply(digits, num);

    }



    // Printing the array in the reverse order.

    for(int i = digits.size() - 1;i >=0; i--)

    {

        cout<    }

}

Python (3.5)

"""

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where N is the given number.

"""





def multiply(digits, x):



    # Initialize carry as zero.

    carry = 0



    # Traversing the whole digits array and updating its values.

    for idx in range(len(digits)):



        prod = x * digits[idx] + carry

        digits[idx] = prod % 10

        carry = prod // 10



    # Iterate till carry is not equal to 0

    while(carry != 0):



        digits.append(carry % 10)

        carry = carry // 10





def factorial(n):



    # Declaring digits array and inserting 1 into digits.

    digits = []

    digits.append(1)

    

    # Multiplying digits array with all numbers from 2 to n.

    for num in range(2, n + 1):

        multiply(digits, num)



    # Printing the array in the reverse order.

    for i in range(len(digits) - 1, -1, -1):

        print(digits[i], end="")

Accepted Answer

24

Accepted Answer

24

Accepted Answer

inTech Mahindra,Software Engineer

Find Factorial of a Number.
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.

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:

Input Format:

Output Format:

Constraints:

Top Tech Mahindra Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Tech Mahindra Software Engineer