Factorial in Java 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 fact to 1 and then iterating from 1 to n, multiplying fact by each number in the loop. 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 already runs in O(n) time and uses O(1) space, it is already optimal. There are no further optimizations needed for this problem.

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 loop variable.
4. After the loop terminates, fact will contain the factorial of n.

Code Implementation

public class Factorial {
    public static int factorial(int n) {
        // Initialize the result to 1
        int fact = 1;
        
        // Iterate from 1 to n
        for (int i = 1; i <= n; i++) {
            // Multiply fact by the current number
            fact *= i;
        }
        
        // Return the computed factorial
        return fact;
    }

    public static void main(String[] args) {
        // Test the factorial function
        int n = 5;
        System.out.println("Factorial of " + n + " is: " + factorial(n)); // 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 fact variable).

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 data type that can handle large numbers if necessary).

Example of edge case:

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

Testing

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

• Simple cases: n = 1, 2, 3
• Edge cases: n = 0
• Large values: n = 20, 50

Example test cases:

System.out.println(factorial(0)); // Output: 1
System.out.println(factorial(1)); // Output: 1
System.out.println(factorial(5)); // Output: 120
System.out.println(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.
• Start with a simple, naive solution and then look for optimizations.
• Consider edge cases and how your solution handles them.
• Practice similar problems to improve your 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 Java. 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:

• Factorial - Wikipedia
• Factorial in Java - GeeksforGeeks
• LeetCode - Coding Challenges