Factorial in JavaScript with O(n) Time Complexity

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

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. However, we can discuss the thought process and how to derive it:

• Initialize a variable fact to 1.
• Use a loop to iterate from 1 to n.
• In each iteration, multiply fact by the current number.
• Return the value of fact after the loop terminates.

Algorithm

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

1. Initialize a variable fact to 1.
2. Use a for loop to iterate from 1 to n.
3. In each iteration, multiply fact by the current number i.
4. After the loop terminates, return the value of fact.

Code Implementation

/**
 * Function to compute the factorial of a non-negative integer n
 * @param {number} n - The non-negative integer
 * @returns {number} - The factorial of n
 */
function factorial(n) {
    // Initialize the result to 1
    let fact = 1;
    
    // Iterate from 1 to n
    for (let i = 1; i <= n; i++) {
        // Multiply fact by the current number i
        fact *= i;
    }
    
    // Return the computed factorial
    return fact;
}

// Example usage:
console.log(factorial(5)); // Output: 120

Complexity Analysis

The time complexity of this algorithm is O(n) because we have a single loop that iterates from 1 to n. The space complexity is O(1) because we are using a constant amount of extra space (the variable fact).

Edge Cases

Potential edge cases include:

• n = 0: The factorial of 0 is defined to be 1.
• Large values of n: Ensure that the algorithm handles large values without overflow (JavaScript handles large integers with its Number type, but for extremely large values, consider using BigInt).

Example edge case:

Input: n = 0
Output: 1
Explanation: 0! = 1

Testing

To test the solution comprehensively, include a variety of test cases:

• Simple cases: factorial(1), factorial(2)
• Edge cases: factorial(0)
• Large values: factorial(20)

Example test cases:

console.log(factorial(0)); // Output: 1
console.log(factorial(1)); // Output: 1
console.log(factorial(2)); // Output: 2
console.log(factorial(5)); // Output: 120
console.log(factorial(10)); // Output: 3628800

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the mathematical definition and properties of the problem.
• Break down the problem into smaller, manageable steps.
• Consider edge cases and how to handle them.
• Practice solving similar problems 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 JavaScript. 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.

Additional Resources

For further reading and practice problems related to the topic, consider the following resources:

• JavaScript Number Documentation
• GeeksforGeeks: Factorial in JavaScript
• LeetCode: Coding Challenge Platform