Skip to content

Volume ITechnology

4.0.7 — Factorial and Trailing Zeros ​

Classic · Easy to Medium · LeetCode 172 (Factorial Trailing Zeroes)

The problem ​

  1. Compute n!, read "n factorial". It is 1 \times 2 \times 3 \times \dots \times n. So 5! = 120.
  2. Count how many zeros n! ends with, without computing n!. 10! = 3{,}628{,}800 ends with two zeros.
  3. Compute 100! in a language whose integers hold only about 19 digits.

The factorial counts arrangements. Three books on a shelf can be ordered in 3! = 6 ways. Pick the first book from 3, the second from the 2 left, the last is forced. 3 \times 2 \times 1. By definition 0! = 1, because there is exactly one way to arrange nothing.

1. Computing n! ​

With a loop ​

python
def factorial(n: int) -> int:
    if n < 0:
        raise ValueError("factorial is not defined for negative numbers")
    result = 1                    # (1)
    for i in range(2, n + 1):     # (2)
        result *= i
    return result

print(factorial(5))    # → 120
print(factorial(0))    # → 1
print(factorial(20))   # → 2432902008176640000

(1) Start at 1, not 0. Anything multiplied by 0 stays 0. Starting at 1 also makes 0! and 1! come out as 1 with no special case, because the loop does not run.

(2) Multiply in 2, 3, and so on up to n. Multiplying by 1 changes nothing, so we skip it.

With recursion ​

n! = n \times (n-1)!. The problem contains a smaller copy of itself, which is Move 5 from 4.0.0.

python
def factorial_rec(n: int) -> int:
    if n <= 1:
        return 1                         # base case
    return n * factorial_rec(n - 1)      # smaller copy

print(factorial_rec(6))   # → 720

Which is better? The loop. The recursive version keeps one unfinished call on the stack for each number, so it uses O(n) memory. Python stops recursion at about 1,000 calls by default. So factorial_rec(5000) crashes with RecursionError, while the loop handles it easily. Interviewers often ask which one is better, and this is the reason.

How big it gets ​

Factorials grow faster than any power. 10! is about 3.6 million. 20! is about 2.4 \times 10^{18}, which is close to the limit of a 64-bit integer. 21! does not fit in one. 100! has 158 digits. Python's integers grow as needed, so Python prints all of them. In Java or C, long overflows at 21!.

2. Trailing zeros without computing n! ​

What makes a zero at the end ​

A number ends in zero when it is divisible by 10. Every 10 is 2 \times 5. So each trailing zero needs one 2 and one 5 among the factors of n!.

Among 1, 2, \dots, n, every second number gives a factor 2. Only every fifth number gives a 5. So 2s are always plentiful, and 5s are what run out first. The number of trailing zeros is just the number of 5s in the prime factorisation of n!.

Counting the 5s ​

Take n = 100.

  • Every multiple of 5 gives at least one 5. There are 100 // 5 = 20 of them.
  • But 25, 50, 75 and 100 are multiples of 25 = 5 \times 5. They each give a second 5. There are 100 // 25 = 4 of them.
  • Multiples of 125 would give a third 5. There are 100 // 125 = 0 of them.

Total: 20 + 4 + 0 = 24 trailing zeros.

Each multiple of 25 is counted once in the first line and once more in the second. That is exactly right, because it holds two 5s. A multiple of 125 would be counted three times, matching its three 5s.

python
def trailing_zeros(n: int) -> int:
    count = 0
    power = 5
    while power <= n:            # (1)
        count += n // power      # (2)
        power *= 5
    return count

print(trailing_zeros(10))    # → 2
print(trailing_zeros(100))   # → 24
print(trailing_zeros(1000))  # → 249

(1) Go through 5, 25, 125, and so on, while they are not bigger than n.

(2) n // power counts the numbers up to n that hold this power of 5.

A neater version divides n instead of growing the power. It gives the same sum.

python
def trailing_zeros_v2(n: int) -> int:
    count = 0
    while n >= 5:
        n //= 5
        count += n
    return count

print(trailing_zeros_v2(100))   # → 24

For 100: first 100 // 5 = 20, then 20 // 5 = 4, then 4 // 5 = 0 stops it. 20 + 4 = 24.

The loop runs once per power of 5, which is O(\log_5 n) steps. Computing 1000! to count its zeros would mean building a 2,568-digit number. This answers in 4 steps.

The general rule is Legendre's formula, from the French mathematician Adrien-Marie Legendre in 1808. The power of any prime p in n! is \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \dots The brackets \lfloor \ \rfloor mean "round down", which is what // does.

3. 100! without big integers ​

Python has big integers built in, so factorial(100) simply works. Interviewers sometimes ask "how would you do it in C?" The answer is to do what you did at school with long multiplication. Store the number as a list of digits, and multiply the list by each new number, carrying as you go.

python
def big_factorial(n: int) -> str:
    digits = [1]                     # (1) the number 1, digits stored right to left
    for x in range(2, n + 1):
        carry = 0
        for i in range(len(digits)):
            prod = digits[i] * x + carry     # (2)
            digits[i] = prod % 10            # (3)
            carry = prod // 10
        while carry:                         # (4)
            digits.append(carry % 10)
            carry //= 10
    return "".join(map(str, reversed(digits)))   # (5)

print(big_factorial(25))   # → 15511210043330985984000000
print(len(big_factorial(100)))   # → 158

(1) Keep the ones digit first. Then a number that grows only needs new digits at the end of the list, which is cheap.

(2) Multiply one digit by x and add the carry from the digit before. This is one column of long multiplication.

(3) Keep the last digit in this place. Carry the rest to the next place.

(4) After the last digit, the carry may still hold several digits. Add them as new places.

(5) Reverse to print the most significant digit first.

Multiplying 120 (stored as [0, 2, 1]) by 6:

placedigit × 6 + carrykeepcarry
ones0 \times 6 + 0 = 000
tens2 \times 6 + 0 = 1221
hundreds1 \times 6 + 1 = 770

The result is [0, 2, 7], which reads as 720. That is 6!.

Complexity ​

The loop: n multiplications. With fixed-size numbers that is O(n). With growing numbers each multiplication gets slower as the number gets longer, so the real cost is higher. Trailing zeros: O(\log n). The digit-list method: O(n \times d), where d is the number of digits in n!, about 158 for n = 100.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"Loop or recursion: which is better for factorial?" The loop. Recursion keeps one unfinished call in memory for each number. Python also stops recursion at about 1,000 calls, so factorial_rec(5000) crashes. The loop has neither problem.

"How many zeros does 100! end with?" 24. Count the factors of 5: 100 // 5 = 20, and 100 // 25 = 4, so 20 + 4 = 24. The numbers 25, 50, 75 and 100 each hold two 5s, which is why the second step is needed. Saying 20 is the usual mistake.

"Why count 5s and not 2s?" Each trailing zero needs one 2 and one 5. There are always more 2s than 5s. So the 5s run out first, and they decide the count.

"What is 0!?" It is 1. There is exactly one way to arrange zero things. It also keeps the rule 1! = 1 \times 0! true.

"How would you store 100! in C?" Keep the number as a list of digits. Multiply it digit by digit with a carry, like long multiplication on paper.

One thing to volunteer: "Adding two big numbers stored as strings works the same way, digit by digit with a carry."

Next: 4.0.8 Fibonacci, Three Ways. The textbook example of a simple recursion that wastes almost all its time.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet