039 — Factorial¶

Level 3-এ স্বাগতম! এতদিন প্রশ্ন ছিল "উত্তরটা কত?" — এবার থেকে প্রশ্ন বদলে "কত উপায়ে?"। আর সেই "কত উপায়ে"-র সবচেয়ে মৌলিক অস্ত্রটাই factorial। ভয় পেও না, এটা আসলে শুধু পরপর গুণ — কিন্তু এই ছোট জিনিসটাই permutation, combination, Catalan — সব কিছুর শিকড়। ধীরে পড়ো, একবার গেঁথে গেলে পুরো level সহজ হয়ে যাবে।

Source¶

Original source: Classic beginner exercise (counting fundamentals)
Platform: Classic exercise — https://discrete.openmathbooks.org/
Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
Difficulty: Easy
Pattern: n! (factorial / iterative product)
Basic idea inherited from: — (এটাই এই level-এর শুরুর শিকড়, multiplication principle ছাড়া আগে কিছু লাগে না)

1. Problem in simple words¶

একটা non-negative integer n দেওয়া আছে। বের করতে হবে তার factorial, যেটা লেখা হয় n!।

n! মানে হলো 1 থেকে n পর্যন্ত সব সংখ্যার গুণফল:

n! = 1 × 2 × 3 × ... × n

যেমন 5! = 1 × 2 × 3 × 4 × 5 = 120। আর একটা বিশেষ নিয়ম: 0! = 1 (এটা মাথায় গেঁথে নাও, পরে কাজে লাগবে)।

ব্যস, এটুকুই। কিন্তু এই ছোট হিসাবটাই combinatorics-এর প্রায় প্রতিটা formula-তে ফিরে আসবে।

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 টা জিনিসকে কত ভাবে সাজানো যায়" — এটাই এর আসল মানে।

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-এর আত্মীয়

4. Real-life analogy¶

ভাবো তোমার বইয়ের তাকে n টা আলাদা বই, আর তুমি সেগুলো এক সারিতে সাজাচ্ছ।

বাঁদিকের প্রথম জায়গায় যেকোনো বই রাখতে পারো → n রকম
পরের জায়গায় বাকি বই থেকে যেকোনোটা → n−1 রকম
এভাবে শেষ জায়গায় হাতে একটাই বই বাকি → 1 রকম

সব মিলিয়ে তাক সাজানোর মোট উপায় = n × (n−1) × ... × 1 = n!। তাই 3টা বই সাজানো যায় 3! = 6 ভাবে, কিন্তু 5টা বই সাজাতে গেলেই 5! = 120 ভাবে — দেখো কত দ্রুত বাড়ে!

5. Visual explanation¶

প্রথমে দেখো factorial আসলে কীভাবে গুণ জমিয়ে বানানো হয়:

5! কীভাবে জমে:

  শুরু:  result = 1
  × 1 -> 1
  × 2 -> 2
  × 3 -> 6
  × 4 -> 24
  × 5 -> 120     <- উত্তর

5! = 1 × 2 × 3 × 4 × 5 = 120

এবার দেখো ছোট factorial গুলো কত দ্রুত বিশাল হয়:

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 লাগে।

6. Example input and output¶

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 হয় না।

7. Brute force thinking¶

প্রথমেই মাথায় আসে সরাসরি সংজ্ঞা মেনে গুণ করা — 1 থেকে n পর্যন্ত সব সংখ্যা একটা একটা করে গুণ করে যাও:

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! — সব আলাদা করে চাই। তখন প্রতিবার শূন্য থেকে শুরু করলে অনেক গুণ বারবার হয়:

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:

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-এ কাজে লাগবে।

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 ✓।

12. Python solution¶

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¶

def factorial(n):
    if n < 0:
        raise ValueError(...)

প্রথমে পাহারা — negative সংখ্যার factorial হয় না, তাই সেক্ষেত্রে error দিই।

    result = 1

গুণফল জমানোর পাত্র, শুরুর মান 1 (গুণের identity)। এই 1-ই n = 0-এ ঠিক উত্তর দেয়।

    for i in range(2, n + 1):
        result *= i

2 থেকে n পর্যন্ত প্রতিটা সংখ্যা result-এ গুণ করি। (1 দিয়ে শুরু করেছি বলে 1 দিয়ে আবার গুণ করার দরকার নেই — তাই range 2 থেকে।)

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! ছাপে।

14. Output walkthrough¶

চালালে যা ছাপবে:

1
120
3628800
সব test pass!

প্রথম তিন লাইন তিনটা print(factorial(...)) থেকে: 0 → 1, 5 → 120, 10 → 3628800। তার আগের সব assert (math.factorial-এর সাথে cross-check সহ) চুপচাপ pass করেছে। সবশেষে সব test pass! — সব ঠিক।

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¶

0! = 1 ভুলে যাওয়া — অনেকে 0! কে 0 ভাবে। শূন্য জিনিস সাজানোর ঠিক একটাই উপায় (কিছু না করা), তাই 0! = 1।
result 0 দিয়ে শুরু করা — তাহলে সব গুণ 0 হয়ে যাবে! গুণফলের শুরু সবসময় 1।
Negative n দিতে ভুলে যাওয়া — factorial(-3) অর্থহীন; চাইলে আগে check করো।
Overflow না ভাবা (অন্য ভাষায়) — Python-এ integer যত বড় হোক চলে, কিন্তু C++/Java-তে 21! ই long long ছাড়িয়ে যায়। বড় n + mod চাইলে Level 2-এর modular pipeline।
বারবার শূন্য থেকে হিসাব — অনেক factorial লাগলে table বানাও, প্রতিবার নতুন করে গুণ কোরো না।

18. Harder problems that inherit this idea¶

040 — Permutation Basic (এই repo) — n!-এর প্রথম r ধাপ নিয়ে nPr।
041 — Combination Basic (এই repo) — nPr-কে r! দিয়ে ভাগ করে nCr।
LeetCode — Permutation Sequence (https://leetcode.com/problems/permutation-sequence/) — k-তম permutation বের করতে factorial-এর সরাসরি ব্যবহার।

19. Pattern learned¶

Iterative product with identity 1 — গুণফল জমাতে হলে result = 1 দিয়ে শুরু করে loop-এ গুণ। আর বড় শিক্ষা: factorial মানে "n টা জিনিস কত ভাবে সাজানো যায়", আর n! = n × (n−1)! — এই recurrence-ই permutation/combination-এর ভিত্তি।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "n! = 1×2×...×n, মানে n জিনিস সাজানোর উপায়; result = 1 দিয়ে শুরু করে গুণ, আর 0! = 1 — এটাই পুরো combinatorics-এর ভিত।"

পরের ধাপ → 040 — Permutation Basic (n!-এর প্রথম কয়েক ধাপ নিয়ে "কতভাবে সাজানো যায়")।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নয় — বরং "common interview pattern" / "Google-style pattern"।