Start learning free

LESSON 140 OF 410 · LOOPS & GLOBAL VARIABLES

Factorial in Python 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

    PYTHON · LOOPS & GLOBAL VARIABLES

    Factorial in Python, 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.

    We initialize a variable fact to 1 and then iterate from 1 to n, multiplying fact by the current number in each iteration.

    Algorithm

    1. Initialize fact to 1.
    2. Iterate from 1 to n.
    3. In each iteration, multiply fact by the current number.
    4. Return fact after the loop ends.

    Code Implementation

    def factorial(n):
    # Initialize the result to 1
    fact = 1
    
    # Iterate from 1 to n
    for i in range(1, n + 1):
        # Multiply fact by the current number
        fact *= i
    
    # Return the computed factorial
    return fact

# Example usage
n = 5
print(factorial(n))  # Output: 120

    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 are using a constant amount of extra space regardless of the input size.

    Edge Cases

    One important edge case is when n is 0. By definition, 0! is 1. Our algorithm handles this case correctly because the loop does not execute, and fact remains 1.

    # Edge case
print(factorial(0))  # Output: 1

    Testing

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

    • Simple cases: n = 1, 2, 3
    • Edge case: n = 0
    • Large values: n = 10, 20
    # Simple cases
print(factorial(1))  # Output: 1
print(factorial(2))  # Output: 2
print(factorial(3))  # Output: 6

# Edge case
print(factorial(0))  # Output: 1

# Large values
print(factorial(10))  # Output: 3628800
print(factorial(20))  # Output: 2432902008176640000

    Thinking and Problem-Solving Tips

    When approaching problems like this, it's important to:

    • Understand the mathematical definition and properties of the problem.
    • Start with a simple, naive solution and then optimize if necessary.
    • Consider edge cases and test your solution thoroughly.

    Conclusion

    In this blog post, we discussed how to compute the factorial of a non-negative integer using an iterative approach in Python. 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

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