Problem Statement

You are given an integer n. Return the value of n! or n factorial.

Factorial of a number is the product of all positive integers less than or equal to that number.

Examples

Example 1:

Input: n = 2
Output: 2

Explanation: 2! = 2 * 1 = 2.

Example 2:

Input: n = 0
Output: 1

Explanation: 0! is 1.

Approaches

1️⃣ Iterative Approach

Intuition:

Given a number, its factorial can be found by multiplying all positive integers starting from 1 to the given number. We use a loop to calculate the factorial by multiplying the numbers from 1 to n.

Approach:

1. Initialize a variable with 1 that will store the factorial of the given number.
2. Start iterating from 1 to the given number, and in every pass multiply the variable with the current number.
3. After the iterations are completed, the variable storing the answer can be returned.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:

    /* Function to find the
    factorial of a number*/
    int factorial(int n) {
        // Variable to store the factorial
        int fact = 1;

        // Iterate from 1 to n
        for(int i = 1; i <= n; i++) {
            // Multiply fact with current number
            fact = fact * i;
        }
        
        // Return the factorial stored
        return fact;
    }
};

int main()
{
    int n = 4;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    // Function call to find the factorial of n
    int ans = sol.factorial(n);
    
    cout << "The factorial of given number is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) – Iterating once from 1 to N.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.

2️⃣ Recursive Approach

We could make use of the recursion.

The intuition is that the factorial of a number n can be broken down into smaller subproblems, specifically the factorial of n - 1.

Approach:

1. Base Case: The base case is when n = 0 or 1. By definition, 0! = 10!=10! = 1 . This is the condition where recursion stops.

2. Recursive Case: For n > 0, we can express n! as:

   n!=n×(n−1)!

   This recursive case breaks down the problem into smaller subproblems, eventually reaching the base case.

3. Recursive Function: The function calls itself with the argument n-1 until the base case is reached.

Code:

#include <iostream>

int factorialRecursive(int n) {
    // Base case: factorial of 0 is 1
    if (n == 0) {
        return 1;
    }
    // Recursive case: n * factorial of (n-1)
    return n * factorialRecursive(n - 1);
}

int main() {
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;

    int result = factorialRecursive(n);
    std::cout << "Factorial of " << n << " is: " << result << std::endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • The function makes nnn recursive calls, each reducing the problem size by one. Hence, the time complexity is linear with respect to n.
• Space Complexity: O(n)
  • The space complexity is also O(n) due to the recursion stack. Each recursive call adds a new frame to the stack until the base case is reached, resulting in nnn frames at the maximum depth.