Find Nth Factorial

Difficulty: Easy

Understanding The Problem

Problem Description

Write a program to find the factorial of a given number n.

Problem Note

• n is a non-negative integer.
• Factorial of a non-negative integer n is the multiplication of all integers smaller than or equal to n

Example

Input: n = 6
Output: 720
Explanation: Factorial of 6 is 6*5*4*3*2*1 which is 720.

Solution

1. Recursive Solution: For f(x), return 1 when x is 0, otherwise return x*f(x-1)
2. Iterative Solution: Iterate from 1 to x and maintain a factorial variable.

You can try the problem here.

1. Recursive Solution

We have to find the factorial of a number. Mathematically, the factorial of a number is the product from 1 to that number.

i.e. factorial(Z) = 1 x 2 x 3 x 4 . . . x (Z-2) x (Z-1) x Z

Looking over the above equation, we can conclude that the factorial(Z) = factorial(Z-1) x Z

Now, the equation seems like a recursive structure, where factorial is a function and we have to find the factorial of Z. Now, We know that the factorial of 0 is 1 and factorial doesn’t exist for -ve numbers. We can use this as a base case of the recursive function.

Base Case

Now think about the base case, where the function will directly give you results without breaking it again into sub-problem.

fact(5) 
= 5 * fact(4) 
= 5 * 4 * fact(3) 
= 5 * 4 * 3 * fact(2) 
= 5 * 4 * 3 * 2 * fact(1) 
= 5 * 4 * 3 * 2 * 1 * fact(0)

The factorial of a negative number is not defined, so fact(0) is the smallest version of the factorial problem where our solution will terminate. Here n = 0 is the base case which will return 1. Since 0! = 1.

To understand more about recursion, refer here.

Solution Steps

1. Create a recursive function factorial(Z)
2. Return 1 when Z is 0.
3. Otherwise, return Z * factorial(Z-1)

Pseudo Code

int findFactorial(int n) {
    if(n is 0)
        return 1
    return n * (findFactorial(n-1))
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Critical Ideas To Think

• How did we define the recursive structure?
• Why we returned 1 when n is 1?
• Why is the space complexity is of O(n)? Answer: The recursive function uses stack space and in this case, we are recursively calling the function until n reaches to 0 and that will create n stack frames in the memory.
• Can you draw the recursion tree for this case?

2. Iterative Solution

Instead of going recursive, we can use the logic of factorial in the way we do it in our notebooks and that is multiplying numbers from 1 to n.

So, the straight forward way is to use a for loop and iterate till n while maintaining a variable that will store the factorial.

Solution Steps

• Create a factorial variable and initialize it with 1
• Create a for loop and iterate from 1 to n
• In each iteration, multiply factorial with i
• Return factorial

Pseudo Code

int findFactorial(int n) {
    int factorial = 1
    for(int i = 1 to i <= n){
         factorial = factorial * i
    }
    return factorial
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas To Think

• Why we started the iteration from 1 while the base case in recursive function was n is 0 ?
• According to you, what should be the maximum number for which you can find the factorial if you are using a single processor system and using some data structure like Big integer?

Comparison Of Different Solutions

Suggested Problems To Solve

• Print numbers n to 1 using a recursive function
• Find a minimum element in sorted and rotated array
• Recursive Insertion Sort
• Median of two sorted array of same size
• Inversion count in an array

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

Happy Coding!

Enjoy Algorithms!