Factorial

Problem Link : factorial

Problem Statement

You are given a positive integer n.
Your task is to compute the factorial of n.

The factorial of a non-negative integer n is defined as:
n! = 1 × 2 × 3 × ... × (n - 1) × n
Special case: 0! = 1

Examples

Example 1:

• Input: n = 5

• Output: 120

• Explanation: 1 × 2 × 3 × 4 × 5 = 120

Example 2:

• Input: n = 4

• Output: 24

• Explanation: 1 × 2 × 3 × 4 = 24

Constraints

• 0 ≤ n ≤ 12

Note: Since 12! = 479001600, the result safely fits in a 32-bit signed integer.

Intuition

The factorial of n can be computed using:

• Recursion: Define factorial(n) = n × factorial(n - 1) with base case factorial(0 or 1) = 1

• Iteration: Multiply numbers from 1 to n in a loop

This problem uses the recursive approach, which is concise and elegant for small values of n.

Approach (Recursive)

1. Base case:

   • If n <= 1, return 1 (since 0! = 1 and 1! = 1)

2. Recursive step:

   • Return n × factorial(n - 1)

Java Code

class Solution {
    static int factorial(int n) {
        if (n <= 1) return 1;          // Base case
        return n * factorial(n - 1);   // Recursive case
    }
}

Dry Run

Input: n = 4

Call Stack:

factorial(4)
→ 4 * factorial(3)
→ 4 * (3 * factorial(2))
→ 4 * (3 * (2 * factorial(1)))
→ 4 * (3 * (2 * 1)) = 24

Output: 24

Time Complexity

• O(n) — One recursive call per number from n down to 1

Space Complexity

• O(n) — Due to recursion stack

Alternative (Iterative Approach)

An iterative version avoids recursion stack overhead:

static int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Conclusion

The recursive approach is clean and appropriate within the problem’s constraint range. For larger values of n, the iterative approach would be more memory-efficient, but for n ≤ 12, recursion is perfectly valid and intuitive.