Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Multiply the integers 1 through n into a running product. The loop is O(n); the real interview point is overflow — a Java long overflows past 20!, so for large n you must switch to BigInteger (or Python's unbounded ints).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you handle the base cases (0! and negatives) cleanly and — more importantly — whether you proactively recognize that the product blows past a 64-bit integer almost immediately.
Where candidates slip
Seeding the accumulator at 0, forgetting 0! = 1, or confidently returning a long for n = 25 without noticing it has silently overflowed to garbage.
How to stand out
State the overflow boundary precisely (20! fits in a long, 21! doesn't), then offer BigInteger as the exact-arithmetic fix and mention the modular variant for competitive-style constraints.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCompute n!Is n ≤ 20?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Iterative Product with long (Baseline)
1Hint 1Explore hintHide hint
Factorial is just repeated multiplication. What's the smallest amount of state you need to carry across the loop?
2Hint 2Explore hintHide hint
Keep one running product, start it at 1, and multiply by each integer from 2 up to n.
3Hint 3Explore hintHide hint
Now ask yourself: how large is the result for n = 25, and does a 64-bit long still hold it?
A · Core idea
Carry one accumulator, seed it at 1, and walk k from 2 to n, multiplying as you go. After the loop the accumulator holds n!.
Why the accumulator starts at 1. Factorial is a product, and the identity for multiplication is 1. Seeding at 1 makes 0! and 1! both return 1 without any special-casing — the loop body simply never runs (for n = 0) or runs once with k = 2 skipped. Seed it at 0 instead and every answer collapses to 0, because anything times zero is zero. This is the single most common beginner bug on this problem.
Why we loop from 2, not 1. Multiplying by 1 is a no-op, so starting k at 2 saves one iteration and reads more clearly. Starting at 1 is also correct — just slightly wasteful.
Why this baseline is dangerous past n = 20. A signed 64-bit long tops out near 9.2 × 10¹⁸. Since 20! ≈ 2.4 × 10¹⁸ fits but 21! ≈ 5.1 × 10¹⁹ does not, the multiply at k = 21 wraps around silently — no exception, just a wrong (often negative) number. The interviewer is watching for whether you catch this before shipping. Say it out loud: "this is correct only for n ≤ 20; beyond that I need BigInteger."
Why iterative beats naive recursion here. A recursive factorial(n) = n * factorial(n-1) pushes n stack frames. For large n that's wasted memory and a stack-overflow risk, with zero upside — the iterative loop does the same multiplications in O(1) space.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5Array state
k=2
1 × 2 = 2
120C · Code with teaching comments
Reference implementation previewpublic long factorial(int n) { if (n < 0) { throw new IllegalArgumentException("factorial is undefined for negative n"); } long result = 1; // 0! and 1! both fall out of this seedExplore the full codeHide the full code
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The arithmetic is trivial; the whole interview lives in the type system. Naming the exact overflow boundary (20! is the last factorial that fits in a long) signals that you think about machine limits, not just math.
ComplexityO(n) time, O(1) space — A single loop from 2 to n does n−1 multiplications, each O(1) on a fixed-width long. No auxiliary storage beyond the accumulator.
E · Edge cases and pitfalls3Seeding the accumulator at 0 — every answer becomes 0.Explore edge casesHide edge cases
Pitfalls
- Seeding the accumulator at 0 — every answer becomes 0.
- Returning a long for n >= 21 without noticing the silent overflow.
- Using recursion and blowing the call stack for large n with no benefit.
Approach 2 of 2 · Optimal
BigInteger / Arbitrary Precision (Optimal for large n)
1Hint 1Explore hintHide hint
The loop is identical — only the type of the accumulator changes. What Java type holds integers of unlimited size?
2Hint 2Explore hintHide hint
Use BigInteger, seed it at BigInteger.ONE, and multiply by BigInteger.valueOf(k) each step.
3Hint 3Explore hintHide hint
In Python you already have this for free — its ints are arbitrary precision, so the baseline loop is already optimal.
A · Core idea
The algorithm does not change — only the container does. Swap the fixed-width long for a type that grows to fit any integer, and the same 1-through-n product now stays exact for arbitrarily large n.
Why a different type, not a different algorithm. Overflow is not a logic error in the loop; it's the hardware running out of bits. BigInteger in Java (and the built-in int in Python) stores numbers as a variable-length sequence of machine words, so it never wraps — it just allocates more space. The control flow, the seed, the multiplication order are all identical to the baseline.
Why the complexity story changes. With a long, each multiply was O(1) because the operand width was fixed. With BigInteger, the product after k steps has roughly k log k bits, so multiplying it by the next integer is no longer constant time. The honest complexity is "O(n) multiplications on numbers that themselves grow," and the output occupies O(n log n) bits. Don't claim O(n) flatly — interviewers like the precision.
Why Python needs no change. Python's int is already arbitrary precision, so the baseline loop is the optimal solution in Python. Mentioning this difference between the two languages is a small but real signal that you understand each runtime's number model rather than memorizing one.
When even BigInteger is the wrong tool. If the problem only wants n! mod m, building the full number wastes enormous memory. There you multiply under the modulus each step and keep numbers small — see the anti-signals.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 21Interactive diagram
Why the long wraps and BigInteger doesn't
k=20Past 20! the fixed-width register has no more bits; BigInteger allocates more.
51090942171709440000C · Code with teaching comments
D · Why it works and complexityO(n) multiplications timeO(n log n) bits for the result spaceOpen the invariant and proofExplore the proofHide the proof
Overflow is a storage problem, not a math problem. The fix is to change the type, not the loop — recognizing that distinction is exactly what separates a candidate who patches symptoms from one who understands the cause.
ComplexityO(n) multiplications time, O(n log n) bits for the result space — There are still n−1 multiplications, but each operates on a number with up to O(n log n) bits, so individual multiplies are no longer O(1). The result itself needs O(n log n) bits of storage — that's the true space cost, not the loop.
E · Edge cases and pitfalls6n = 0 — Loop body never executes; returns the seed BigInteger.ONE = 1. Correct by definition.Explore edge casesHide edge cases
Edge cases handled
n = 0Loop body never executes; returns the seed BigInteger.ONE = 1. Correct by definition.n = 1Loop runs for k from 2 to 1, i.e. never; returns 1.n = 21Exceeds Long.MAX_VALUE; BigInteger returns the exact 51090942171709440000 where a long would have wrapped.
Pitfalls
- Forgetting BigInteger is immutable — calling result.multiply(...) without reassigning result discards the answer.
- Claiming O(n) time flatly — the multiplies grow as the number grows.
- Using BigInteger when the problem only wanted n! mod m — wasteful memory.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewimport java.math.BigInteger; public BigInteger factorial(int n) { if (n < 0) { throw new IllegalArgumentException("factorial is undefined for negative n");Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Seeding the accumulator at 0
Factorial is a product, so the identity must be 1. Start at 0 and every multiply keeps the answer pinned at 0.
Explore the code comparisonHide the code comparison
Seeding the accumulator at 0
Factorial is a product, so the identity must be 1. Start at 0 and every multiply keeps the answer pinned at 0.
Don't write this
long result = 0;
for (int k = 2; k <= n; k++) {
result *= k; // 0 * anything = 0
}
return result;Write this instead
long result = 1;
for (int k = 2; k <= n; k++) {
result *= k;
}
return result;2Ignoring overflow on a long
21! exceeds Long.MAX_VALUE, so the multiply wraps to a wrong value with no exception. Switch the accumulator to BigInteger when n can exceed 20.
Explore the code comparisonHide the code comparison
Ignoring overflow on a long
21! exceeds Long.MAX_VALUE, so the multiply wraps to a wrong value with no exception. Switch the accumulator to BigInteger when n can exceed 20.
Don't write this
long result = 1;
for (int k = 2; k <= n; k++) {
result *= k; // wrong for n >= 21
}
return result;Write this instead
BigInteger result = BigInteger.ONE;
for (int k = 2; k <= n; k++) {
result = result.multiply(BigInteger.valueOf(k));
}
return result;3Not rejecting negative input
Factorial is undefined for negatives. A naive loop just returns the seed 1, hiding the bad input instead of surfacing it.
Explore the code comparisonHide the code comparison
Not rejecting negative input
Factorial is undefined for negatives. A naive loop just returns the seed 1, hiding the bad input instead of surfacing it.
Don't write this
def factorial(self, n: int) -> int:
result = 1
for k in range(2, n + 1):
result *= k
return result # returns 1 for n = -5, silently wrongWrite this instead
def factorial(self, n: int) -> int:
if n < 0:
raise ValueError("factorial is undefined for negative n")
result = 1
for k in range(2, n + 1):
result *= k
return resultRevise
Carry the pattern into the interview
Pattern to remember
Iterative running product with an overflow story
Code pattern to memorize
result = 1
for k in 2..n:
result *= k
return result # long overflows past 20! → use BigIntegerRules to remember
- 1Define
0! = 1and1! = 1— the empty product is 1, not 0. Returning 0 here is the classic off-by-base bug. - 2A signed 64-bit
longholds up to20!;21!silently overflows to a wrong (often negative) value. Name this out loud. - 3Start the accumulator at
1, never0— multiplying by a zero seed makes every answer 0. - 4Reject negative
nexplicitly: factorial is undefined for negatives, so throw or return an error rather than looping zero times and pretending it's1. - 5Prefer the iterative loop over naive recursion — recursion adds O(n) stack frames and risks a stack overflow for large n with no benefit.
Use this pattern when
- You need an exact product of consecutive integers 1..n
- Counting permutations / arrangements where order matters
- Building combinatorics (nCr, nPr) where factorials appear in numerator and denominator
- The interviewer is probing whether you reason about integer overflow
Choose another pattern when
- n is large and you only need the answer modulo a prime → multiply under the modulus, never compute the full factorial
- You only need trailing zeros of n! → count factors of 5, don't build the number
- You need n! / (n−k)! → cancel the common terms, don't compute both factorials
Interview takeaway
Factorial is a one-line loop dressed up as an interview question — the grading happens entirely on whether you mention overflow and reach for BigInteger before the interviewer has to ask.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternIterative running product with an explicit overflow narrative. The same accumulate-in-a-loop shape underlies power, sum, and prefix-product problems; the distinguishing skill here is recognizing when a fixed-width integer can no longer hold the result and reaching for arbitrary-precision arithmetic.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Factorial Trailing ZeroesCount the number of trailing zeros in n! by counting factors of 5 — never build the full number.
- n! modulo a prime pMultiply under the modulus each step to keep numbers small; pairs with Fermat's little theorem for division.
- Number of digits in n!Use the sum of log10(k) for k from 1 to n, then floor + 1 — avoids building the giant number.
Same pattern