Problem link ও উৎস
- **Original source:** Classic beginner exercise (counting fundamentals)
- **Platform:** Classic exercise —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Easy
- **Pattern:** n! (factorial / iterative product)
- **Basic idea inherited from:** — (এটাই এই level-এর শুরুর শিকড়, multiplication principle ছাড়া আগে কিছু লাগে না)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা non-negative integer `n` দেওয়া আছে। বের করতে হবে তার **factorial**, যেটা লেখা হয় `n!`।
`n!` মানে হলো 1 থেকে n পর্যন্ত সব সংখ্যার গুণফল:
```text
n! = 1 × 2 × 3 × ... × n
```
যেমন `5! = 1 × 2 × 3 × 4 × 5 = 120`। আর একটা বিশেষ নিয়ম: `0! = 1` (এটা মাথায় গেঁথে নাও, পরে কাজে লাগবে)।
ব্যস, এটুকুই। কিন্তু এই ছোট হিসাবটাই combinatorics-এর প্রায় প্রতিটা formula-তে ফিরে আসবে।
### Input ও output {#6-example-input-and-output}
```text
input -> output
-----------------
0 -> 1 (0! = 1, বিশেষ নিয়ম)
1 -> 1
3 -> 6 (1×2×3)
5 -> 120
6 -> 720
10 -> 3628800
```
দুটো edge case খেয়াল করো: **0! = 1** (অনেকে ভুল করে 0 ভাবে), আর factorial শুধু **non-negative** সংখ্যায় সংজ্ঞায়িত — negative n-এর factorial হয় না।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার বইয়ের তাকে `n` টা আলাদা বই, আর তুমি সেগুলো এক সারিতে সাজাচ্ছ।
- বাঁদিকের প্রথম জায়গায় যেকোনো বই রাখতে পারো → n রকম
- পরের জায়গায় বাকি বই থেকে যেকোনোটা → n−1 রকম
- এভাবে শেষ জায়গায় হাতে একটাই বই বাকি → 1 রকম
সব মিলিয়ে তাক সাজানোর মোট উপায় = `n × (n−1) × ... × 1 = n!`। তাই 3টা বই সাজানো যায় 3! = 6 ভাবে, কিন্তু 5টা বই সাজাতে গেলেই 5! = 120 ভাবে — দেখো কত দ্রুত বাড়ে!
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা এই level-এর প্রথম problem, তাই এর উপরে দাঁড়ানোর মতো আগের counting-problem নেই (তাই "inherited from: —")।
বরং এর পেছনে আছে একটাই সরল ধারণা — **multiplication principle**: কাজটা যদি ধাপে ধাপে হয় আর প্রতি ধাপের choice-সংখ্যা জানা থাকে, তাহলে মোট উপায় = ধাপগুলোর গুণফল। Factorial সেই নিয়মেরই সবচেয়ে পরিষ্কার রূপ।
আর এটাই হবে অনেক কিছুর বীজ:
- **040 (nPr)** — পুরো n! না, প্রথম r ধাপের গুণ
- **041 (nCr)** — nPr-কে আবার r! দিয়ে ভাগ
- **050 (derangement)**-ও factorial-এর আত্মীয়
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **multiplication principle** (গুণের নিয়ম)। ভাবো `n` জনকে এক লাইনে দাঁড় করাচ্ছ:
- প্রথম জায়গায় বসাতে পারো n জনের যে কাউকে → n choice
- দ্বিতীয় জায়গায় বাকি n−1 জনের যে কাউকে → n−1 choice
- তৃতীয় জায়গায় n−2 choice... এভাবে শেষ জায়গায় 1 choice
প্রতিটা ধাপ আগেরটার উপর নির্ভর করছে না (just কমে যাচ্ছে), তাই মোট উপায় = `n × (n−1) × (n−2) × ... × 1 = n!`। তাই factorial মানেই হলো **"n টা জিনিসকে কত ভাবে সাজানো যায়"** — এটাই এর আসল মানে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমেই মাথায় আসে সরাসরি সংজ্ঞা মেনে গুণ করা — 1 থেকে n পর্যন্ত সব সংখ্যা একটা একটা করে গুণ করে যাও:
```python
def factorial_brute(n):
result = 1
for i in range(1, n + 1): # 1, 2, 3, ..., n
result = result * i
return result
```
`n = 0` হলে loop একবারও চলে না, তাই `result` শুরুর মান 1-ই থাকে → ঠিক `0! = 1` পাওয়া যায়। চমৎকার — কোনো আলাদা if লাগল না।
এটা আসলে আমাদের বই-সাজানোর analogy-টাই: প্রতি ধাপে যত choice, সেটা গুণ করে জমাচ্ছি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
আসলে এই loop খুব slow নয় — মাত্র n বার চলে, মানে O(n)। ছোট n-এ এটাই যথেষ্ট।
সমস্যা হয় তখন, যখন **একই program-এ বারবার বিভিন্ন factorial লাগে**। ধরো তোমাকে 1!, 2!, 3!, ..., 1000! — সব আলাদা করে চাই। তখন প্রতিবার শূন্য থেকে শুরু করলে অনেক গুণ বারবার হয়:
```text
factorial(5) হিসাব করে: 1×2×3×4×5
factorial(6) আবার শুরু: 1×2×3×4×5×6 <- 1×2×3×4×5 আবার করল!
```
5! হিসাব করার পর 6! চাইলে আগের কাজটা ফেলে দিয়ে আবার শূন্য থেকে শুরু — এটাই অপচয়। নিচে এর সমাধান।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **n! = n × (n−1)!**। মানে এক ধাপ আগের factorial জানা থাকলে শুধু একবার গুণ করলেই পরেরটা পাওয়া যায়।
তাই যদি অনেকগুলো factorial একসাথে লাগে, একটা **prefix table** বানিয়ে রাখো — `fact[i] = fact[i-1] * i`:
```python
def factorial_table(max_n):
fact = [1] * (max_n + 1) # fact[0] = 1
for i in range(1, max_n + 1):
fact[i] = fact[i - 1] * i
return fact # fact[k] = k! সব k-র জন্য
```
একবার table বানালে যেকোনো `k!` সাথে সাথে `fact[k]` থেকে পড়া যায় — O(1)-এ। এই precompute-pattern-টাই পরে Level 2-এর nCr mod p pipeline-এ ফিরবে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
ছোট্ট কিন্তু গুরুত্বপূর্ণ মোচড়: **`result` শুরু করো 1 দিয়ে, 0 দিয়ে নয়।**
কেন? গুণে নিরপেক্ষ উপাদান (identity) হলো 1 — `x × 1 = x`। তাই খালি গুণফলের শুরুর মান 1। এটা একসাথে দুটো জিনিস সামলায়:
- সাধারণ n-এ গুণ ঠিকঠাক জমে
- `n = 0`-এ loop না চলায় `result` 1-ই থাকে → আপনাআপনি `0! = 1` বেরিয়ে আসে
এই "গুণের জন্য 1, যোগের জন্য 0 দিয়ে শুরু" অভ্যাসটা গেঁথে নাও — পরের সব product-based counting-এ কাজে লাগবে।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো factorial আসলে কীভাবে গুণ জমিয়ে বানানো হয়:
```text
5! কীভাবে জমে:
শুরু: result = 1
× 1 -> 1
× 2 -> 2
× 3 -> 6
× 4 -> 24
× 5 -> 120 <- উত্তর
5! = 1 × 2 × 3 × 4 × 5 = 120
```
এবার দেখো ছোট factorial গুলো কত দ্রুত বিশাল হয়:
```text
n | n!
---+--------
0 | 1 <- বিশেষ নিয়ম: কিছুই না সাজানোর 1 উপায়
1 | 1
2 | 2
3 | 6
4 | 24
5 | 120
6 | 720
7 | 5040
10 | 3628800 <- মাত্র 10-এই 36 লক্ষ পেরিয়ে গেল!
```
লক্ষ করো — n সামান্য বাড়লেই n! বিস্ফোরণের মতো বাড়ে। এই দ্রুত বৃদ্ধিই পরে বোঝাবে কেন বড় counting-এ mod লাগে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `n = 4` ধীরে ধীরে চালাই:
| step (i) | result (শুরুতে) | result × i | result (পরে) |
| --- | --- | --- | --- |
| শুরু | — | — | 1 |
| 1 | 1 | 1 × 1 | 1 |
| 2 | 1 | 1 × 2 | 2 |
| 3 | 2 | 2 × 3 | 6 |
| 4 | 6 | 6 × 4 | 24 |
Loop শেষ → `result = 24` → মানে `4! = 24` ✓।
আর `n = 0` হলে: `range(1, 1)` খালি, loop একবারও চলে না, তাই শুরুর `result = 1`-ই ফেরত — `0! = 1` ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def factorial(n):
"""n! (n-এর factorial) ফেরত দেয়। n non-negative হতে হবে।"""
if n < 0:
raise ValueError("factorial শুধু non-negative সংখ্যায় হয়")
result = 1
for i in range(2, n + 1): # 2, 3, ..., n (1 দিয়ে গুণ করা অর্থহীন)
result *= i
return result
def factorial_table(max_n):
"""0! থেকে max_n! পর্যন্ত সব factorial একটা list-এ ফেরত দেয়।"""
fact = [1] * (max_n + 1)
for i in range(1, max_n + 1):
fact[i] = fact[i - 1] * i
return fact
# --- ছোট test গুলো (সব pass করা উচিত) ---
import math
assert factorial(0) == 1 # বিশেষ নিয়ম
assert factorial(1) == 1
assert factorial(3) == 6
assert factorial(5) == 120
assert factorial(6) == 720
assert factorial(10) == 3628800
# math.factorial দিয়ে cross-check (0 থেকে 12 পর্যন্ত)
for k in range(0, 13):
assert factorial(k) == math.factorial(k)
# table version-ও একই উত্তর দেয় কিনা
table = factorial_table(12)
for k in range(0, 13):
assert table[k] == math.factorial(k)
print(factorial(0)) # 1
print(factorial(5)) # 120
print(factorial(10)) # 3628800
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def factorial(n):
if n < 0:
raise ValueError(...)
```
প্রথমে পাহারা — negative সংখ্যার factorial হয় না, তাই সেক্ষেত্রে error দিই।
```text
result = 1
```
গুণফল জমানোর পাত্র, শুরুর মান 1 (গুণের identity)। এই 1-ই `n = 0`-এ ঠিক উত্তর দেয়।
```text
for i in range(2, n + 1):
result *= i
```
2 থেকে n পর্যন্ত প্রতিটা সংখ্যা `result`-এ গুণ করি। (1 দিয়ে শুরু করেছি বলে 1 দিয়ে আবার গুণ করার দরকার নেই — তাই `range` 2 থেকে।)
```text
def factorial_table(max_n):
fact = [1] * (max_n + 1)
for i in range(1, max_n + 1):
fact[i] = fact[i - 1] * i
```
অনেক factorial একসাথে লাগলে — `fact[i] = fact[i-1] × i` নিয়মে পুরো table এক pass-এ ভরে ফেলি। `fact[0]` আগেই 1।
বাকি `assert` লাইনগুলো `math.factorial`-এর সাথে মিলিয়ে নিজেদের চেক করছে — মিল না হলে সেখানেই থেমে error দেবে। সব মিললে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
1
120
3628800
সব test pass!
```
প্রথম তিন লাইন তিনটা `print(factorial(...))` থেকে: 0 → 1, 5 → 120, 10 → 3628800। তার আগের সব `assert` (`math.factorial`-এর সাথে cross-check সহ) চুপচাপ pass করেছে। সবশেষে `সব test pass!` — সব ঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — loop ঠিক n−1 বার চলে (2 থেকে n), প্রতিবার একটা গুণ। সংখ্যাটা যত বড়, ঠিক ততগুলো গুণ।
(সূক্ষ্ম কথা: n! বিশাল হয়ে গেলে প্রতিটা গুণ আর constant-time থাকে না — বড় সংখ্যার গুণে digit-সংখ্যার সাথে সামান্য খরচ বাড়ে। তবে সাধারণ interview-র মাপে আমরা একে O(n) ধরি।)
### অতিরিক্ত জায়গা {#16-space-complexity}
`factorial(n)`-এ **O(1)** — শুধু একটা `result` variable (বিশাল সংখ্যাটার নিজের জায়গা বাদে)।
`factorial_table(max_n)`-এ **O(max_n)** — পুরো table list-এ রাখছি বলে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **0! = 1 ভুলে যাওয়া** — অনেকে 0! কে 0 ভাবে। শূন্য জিনিস সাজানোর ঠিক একটাই উপায় (কিছু না করা), তাই `0! = 1`।
2. **`result` 0 দিয়ে শুরু করা** — তাহলে সব গুণ 0 হয়ে যাবে! গুণফলের শুরু সবসময় 1।
3. **Negative n দিতে ভুলে যাওয়া** — `factorial(-3)` অর্থহীন; চাইলে আগে check করো।
4. **Overflow না ভাবা (অন্য ভাষায়)** — Python-এ integer যত বড় হোক চলে, কিন্তু C++/Java-তে 21! ই long long ছাড়িয়ে যায়। বড় n + mod চাইলে Level 2-এর modular pipeline।
5. **বারবার শূন্য থেকে হিসাব** — অনেক factorial লাগলে table বানাও, প্রতিবার নতুন করে গুণ কোরো না।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **040 — Permutation Basic** (এই repo) — n!-এর প্রথম r ধাপ নিয়ে nPr।
- **041 — Combination Basic** (এই repo) — nPr-কে r! দিয়ে ভাগ করে nCr।
- **LeetCode — Permutation Sequence** (