Factorial in C++ with O(n) Time Complexity

Given a non-negative integer n return the factorial of n, also denoted as n!

n! = 1 * 2 * 3 * ... * (n - 1) * n

Example:

Input: n = 5
Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120

Note:

Your algorithm should run in O(n) time and use O(1) space.

Understanding the Problem

The core challenge of this problem is to compute the factorial of a given non-negative integer n. The factorial of a number is the product of all positive integers less than or equal to that number. Factorials are commonly used in permutations, combinations, and other mathematical computations.

Potential pitfalls include handling the edge case where n is 0, as 0! is defined to be 1.

Approach

To solve this problem, we can use an iterative approach. The naive solution involves using a loop to multiply the numbers from 1 to n. This approach is straightforward and efficient for this problem.

Naive Solution

The naive solution involves initializing a variable to 1 and then iterating from 1 to n, multiplying the variable by the current number in each iteration. This solution is optimal for this problem as it runs in O(n) time and uses O(1) space.

Optimized Solution

Since the naive solution is already optimal for this problem, there is no need for further optimization. The iterative approach is both time-efficient and space-efficient.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize a variable fact to 1.
Iterate from 1 to n.
In each iteration, multiply fact by the current number.
After the loop ends, fact will contain the factorial of n.

Code Implementation

#include <iostream>
using namespace std;

// Function to compute factorial
int factorial(int n) {
    int fact = 1; // Initialize fact to 1
    for (int i = 1; i <= n; ++i) {
        fact *= i; // Multiply fact by i
    }
    return fact; // Return the computed factorial
}

int main() {
    int n;
    cout << "Enter a non-negative integer: ";
    cin >> n;
    cout << "Factorial of " << n << " is " << factorial(n) << endl;
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n) because we have a single loop that iterates n times. The space complexity is O(1) because we only use a constant amount of extra space for the variable fact and the loop counter.

Edge Cases

Potential edge cases include:

n = 0: The factorial of 0 is defined to be 1.
Large values of n: Ensure that the solution handles large values without overflow (consider using a larger data type if necessary).

Testing

To test the solution comprehensively, consider the following test cases:

n = 0: Expected output is 1.
n = 1: Expected output is 1.
n = 5: Expected output is 120.
n = 10: Expected output is 3628800.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to understand the mathematical definition and properties of the concept involved. For factorials, knowing that 0! is 1 and that the factorial function grows very quickly can help in designing efficient algorithms.

Practice solving similar problems and study different algorithms to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to compute the factorial of a non-negative integer using an iterative approach in C++. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.