Problem

Given a non-negative integer n, compute n! (n factorial), defined as the product of all positive integers up to n:

n! = n * (n-1) * ... * 2 * 1, with 0! = 1.

Factorial grows very quickly; for moderate n the result will overflow fixed-size integer types. Use arbitrary-precision types (e.g., Python int, Java BigInteger) when large n must be supported.

Examples

1
2
3

Input: n = 3
Output: 6
Explanation: 3! = 3 * 2 * 1 = 6

1
2
3

Input: n = 0
Output: 1
Explanation: 0! is defined as 1

Solution

Two standard ways to compute factorial are shown below: recursion and iterative multiplication. Both compute the same result; recursion is concise but can overflow the call stack for deep recursion, while iteration is iterative and typically preferred in production.

Method 1 — Recursion

Intuition

Factorial satisfies the recurrence n! = n * (n-1)! with base case 0! = 1. Recursion directly implements this definition.

Approach

  • If n == 0 or n == 1, return 1.
  • Otherwise return n * factorial(n-1).
  • Be mindful of recursion depth and integer overflow; for large n use arbitrary-precision arithmetic or an iterative approach.

Code

1
2
3
4
5
6
7

class Solution {
public:
    unsigned long long factorial(unsigned int n) {
        if (n <= 1) return 1ULL;
        return n * factorial(n - 1);
    }
};
1
2
3
4
5
6

package main

func Factorial(n uint64) uint64 {
    if n <= 1 { return 1 }
    return n * Factorial(n-1)
}
1
2
3
4
5
6

class Solution {
    public long factorial(int n) {
        if (n <= 1) return 1L;
        return n * factorial(n - 1);
    }
}
1
2
3
4
5
6

class Solution {
    fun factorial(n: Int): Long {
        if (n <= 1) return 1L
        return n * factorial(n - 1)
    }
}
1
2
3
4
5

class Solution:
        def factorial(self, n: int) -> int:
                if n <= 1:
                        return 1
                return n * self.factorial(n - 1)
1
2
3
4
5
6
7

pub struct Solution;
impl Solution {
        pub fn factorial(n: u64) -> u128 {
                if n <= 1 { return 1 }
                (1..=n).product()
        }
}

Complexity

  • ⏰ Time complexity: O(n) — multiplies n numbers.
  • 🧺 Space complexity: O(n) recursion stack for the recursive method; iterative method uses O(1) extra space.

Method 2 — Iterative multiplication (recommended)

Intuition

Compute the product 1 * 2 * ... * n using a simple loop — avoids recursion depth issues and is straightforward to write for arbitrary-precision types.

Approach

  • Initialize ans = 1.
  • For i from 2 to n, set ans *= i.
  • Return ans.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    unsigned long long factorial_iter(unsigned int n) {
        unsigned long long ans = 1ULL;
        for (unsigned int i = 2; i <= n; ++i) ans *= i;
        return ans;
    }
};
1
2
3
4
5
6
7

package main

func FactorialIter(n uint64) uint64 {
    ans := uint64(1)
    for i := uint64(2); i <= n; i++ { ans *= i }
    return ans
}
1
2
3
4
5
6
7
8
9

import java.math.BigInteger;

class Solution {
    public BigInteger factorialBig(int n) {
        BigInteger ans = BigInteger.ONE;
        for (int i = 2; i <= n; i++) ans = ans.multiply(BigInteger.valueOf(i));
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

import java.math.BigInteger

class Solution {
    fun factorialBig(n: Int): BigInteger {
        var ans = BigInteger.ONE
        for (i in 2..n) ans = ans.multiply(BigInteger.valueOf(i.toLong()))
        return ans
    }
}
1
2
3
4
5
6

class Solution:
        def factorial_iter(self, n: int) -> int:
                ans = 1
                for i in range(2, n + 1):
                        ans *= i
                return ans
1
2
3
4
5
6

pub struct Solution;
impl Solution {
        pub fn factorial_iter(n: u64) -> u128 {
                (1..=n).product()
        }
}

Complexity

  • ⏰ Time complexity: O(n) — n-1 multiplications.
  • 🧺 Space complexity: O(1) extra space (or O(n) if using big-integer intermediate allocations depending on the language/runtime).

Notes

  • Factorial values overflow built-in integer types quickly: 20! fits in 64-bit unsigned, 21! does not. Use arbitrary-precision types for larger n.
  • Python’s int is arbitrary-precision by default; Java and Kotlin use BigInteger when needed.
  • Recursion is elegant but can hit recursion depth limits for large n (use iterative for production).