Start learning free

LESSON 140 OF 410 · LOOPS & GLOBAL VARIABLES

Factorial in Java with O(n) Time Complexity

Practice Read the full explanation

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.


Hints:

To compute the factorial, we have to iterate through every value from 1 to n and multiply that value to the product. How can we achieve this?

First of all, we should store this product somewhere as we compute it. That 'somewhere' is a variable, let's name it fact. For example, for n = 4: 
set fact to 1       (fact is initially 1 = 1!)
multiply fact by 2  (now fact is 1 * 2 = 2!)
multiply fact by 3  (now fact is 1 * 2 * 3 = 3!)
multiply fact by 4  (now fact is 1 * 2 * 3 * 4 = 4!)
How can we extend this code to compute the factorial of any value of n?

With a loop! Let's use a for loop and a variable i to iterate through the numbers 1 to n: 
set fact to 1       (fact is initially 1 = 1!)
for i from 1 to n:
	(what should we do here?)
What should we do inside this loop?

Inside the loop, all we should do is multiply fact by i.
When the loop terminates, the answer lies in fact: 
set fact to 1
for i from 1 to n:
	multiply fact by i
return fact


We have a for loop that performs exactly n iterations, thus the Time Complexity is O(n).
The only extra space we use is the variable fact and the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

STEP 1 OF 4
    Ctrl + Enter to check

    JAVA · LOOPS & GLOBAL VARIABLES

    Factorial in Java, explained

    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:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free