Given a non-negative integer n return the factorial of n, also denoted as n!
n! = 1 * 2 * 3 * ... * (n - 1) * nExample:
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.
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.
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.
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.
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.
Here is a step-by-step breakdown of the algorithm:
fact
to 1.fact
by the current loop variable.fact
will contain the factorial of n.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
}
}
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).
Potential edge cases include:
Example of edge case:
Input: n = 0 Output: 1 Explanation: 0! = 1
To test the solution comprehensively, consider the following test cases:
n = 1, 2, 3
n = 0
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
When approaching such problems, consider the following tips:
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.
For further reading and practice problems related to the topic, consider the following resources: