## 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

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

Happy Coding!

Enjoy Algorithms!