012 — Count Factors

011-এ তুমি শিখেছ "একটা সংখ্যা আরেকটা দিয়ে ভাগ যায় কিনা" (a % b == 0)। আজ সেই চেক দিয়েই বড় প্রশ্ন — একটা সংখ্যার মোট কতগুলো factor (divisor) আছে? প্রথমে সরল ভাবে সব সংখ্যা ঘেঁটে গুনব, তারপর এই level-এর সবচেয়ে দামি কৌশল শিখব: O(n) loop-কে O(√n)-এ নামানো। এই √n trick একবার হাতে এলে prime check, factorization — সব জায়গায় ফিরবে। তাই ধীরে, factor-জোড়ার ছবিটা নিজে হাতে আঁকো।

Source

• Original source: Classic beginner exercise
• Platform: Classic exercise
• Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
• Difficulty: Easy
• Pattern: √n factor pairs
• Basic idea inherited from: 011 (Divisibility Rules)

1. Problem in simple words

একটা positive integer n দেওয়া আছে। বলতে হবে তার মোট কতগুলো factor (বা divisor) আছে — মানে কতগুলো সংখ্যা n-কে নিঃশেষে ভাগ করে।

যেমন 12-এর factor: 1, 2, 3, 4, 6, 12 — মোট 6টা। 7-এর factor: 1, 7 — মোট 2টা (কারণ 7 prime)।

আমরা শুধু গুনব কতগুলো, factor-গুলো ছাপতে হবে না (যদিও চাইলে সহজেই ছাপানো যায়)।

2. What is the math idea?

মূল idea — factor রা জোড়ায় আসে, আর সেই জোড়ার ছোট জনটা সবসময় √n-এর এপারে থাকে।

d যদি n-এর factor হয়, তবে n // d-ও factor (কারণ d × (n//d) = n)। তাই factor সবসময় জোড়ায় আসে: (1, 12), (2, 6), (3, 4) — 12-এর জন্য।

12-এর factor জোড়া:
  1 × 12      2 × 6      3 × 4
  \_____/     \____/     \___/
  প্রতিটা জোড়ায় ছোট জন ≤ √12 ≈ 3.46

মূল অন্তর্দৃষ্টি: প্রতি জোড়ার ছোট সদস্য সবসময় ≤ √n (দুজনেই √n-এর চেয়ে বড় হলে গুণফল n ছাড়িয়ে যেত)। তাই 1 থেকে √n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ তুলে নিলেই সব factor পাওয়া যায় — পুরো n পর্যন্ত যাওয়ার দরকার নেই।

3. Which basic idea does this inherit from?

সরাসরি 011 (Divisibility Rules) থেকে।

011-এ শিখেছিলাম একটা মাত্র চেক — n % d == 0 মানে d ভাগ করে n-কে। 012-এ আমরা সেই একই চেক বারবার চালাই, প্রতিটা সম্ভাব্য d-এর জন্য, আর যতবার True পাই ততবার গুনি:

011:  n % d == 0       -> d কি factor? (একবার)
012:  for d: n % d == 0 -> কতগুলো d factor? (বারবার গুনে)

মানে 011 ছিল "ভাগ যায় কিনা" — একটা হ্যাঁ/না; 012 হলো "কতজন ভাগ করে" — সেই হ্যাঁ-গুলো গোনা। 011-এর divisibility চেক না বুঝলে এখানে গোনার ভিত্তিটাই দুর্বল থাকবে।

4. Real-life analogy

ভাবো nটা ইট দিয়ে তুমি একটা আয়তক্ষেত্রাকার দেয়াল বানাতে চাও, একটাও ইট নষ্ট না করে। কত রকম মাপের (লম্বা × চওড়া) দেয়াল বানানো যায়?

• 12টা ইট দিয়ে: 1×12, 2×6, 3×4, 4×3, 6×2, 12×1 — প্রতিটা মাপের একটা পাশ একটা factor
• লক্ষ করো — 2×6 আর 6×2 একই দুটো সংখ্যা, শুধু ঘুরিয়ে। তাই অর্ধেক মাপ গুনে জোড়া ধরে দ্বিগুণ করলেই হয়

মানে প্রতিটা factor হলো একটা সম্ভাব্য "এক পাশের দৈর্ঘ্য", আর তারা স্বাভাবিকভাবেই জোড়ায় আসে (এক পাশ ঠিক করলে অন্য পাশ আপনিই ঠিক)। √n হলো সেই বর্গাকার দেয়ালের বাহু — তার এপারে খুঁজলেই সব জোড়া ধরা পড়ে।

5. Visual explanation

n = 36-এর factor জোড়াগুলো — √36 = 6-এর দু'পাশে কীভাবে আয়নার মতো সাজানো, দেখো:

i (≤ √n)   জোড়ার সঙ্গী n//i
   1    <------->    36
   2    <------->    18
   3    <------->    12
   4    <------->     9
   6    <------->     6   <- √36, জোড়া নিজের সাথে! একবার গোনো
   ^^^^^^^^^^^^
   √n পর্যন্ত খুঁজলেই ডান পাশের সব ধরা পড়ে

মোট: 1,2,3,4,6,9,12,18,36 -> 9টা factor

কেন √n-এই থামি, এক বাক্যে:

যদি i > √n আর n//i > √n হতো -> i × (n//i) > n  -> অসম্ভব!
তাই প্রতি জোড়ার ছোট জন অবশ্যই ≤ √n

6. Example input and output

count_factors(n) — n-এর factor সংখ্যা
-------------------------------------
count_factors(12) -> 6     (1,2,3,4,6,12)
count_factors(7)  -> 2     (1,7 — prime, তাই ঠিক 2)
count_factors(1)  -> 1     (শুধু 1 নিজে)
count_factors(36) -> 9     (perfect square, বিজোড় সংখ্যা!)
count_factors(16) -> 5     (1,2,4,8,16 — perfect square)
count_factors(100)-> 9     (1,2,4,5,10,20,25,50,100)

দুটো মজার সত্য: prime-এর ঠিক 2টা factor (1 আর নিজে), আর perfect square-এর factor সংখ্যা সবসময় বিজোড় (কারণ মাঝের √n নিজের জোড়া — যেমন 36-এ 6×6)। এই perfect-square কেসটাই এই problem-এর সবচেয়ে দামি ফাঁদ।

7. Brute force thinking

সবচেয়ে সৎ, সরাসরি ভাবনা — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা দেখি, যেটা ভাগ করে তাকে গুনি:

def count_factors_brute(n):
    count = 0
    for d in range(1, n + 1):     # 1 থেকে n সব দেখো
        if n % d == 0:            # 011-এর divisibility চেক
            count += 1
    return count

এটা একদম স্বচ্ছ — "factor মানে যে ভাগ করে, তাই সবাইকে জিজ্ঞেস করি কে ভাগ করে।" 011-এর চেক বারবার চালানো ছাড়া কিছু না। ছোট n-এ একদম ঠিক।

8. Why brute force may be slow

সমস্যা একটাই — এই loop ঘোরে পুরো n বার:

• n = 1,000,000 হলে 10 লক্ষ বার loop — তাও হয়তো চলে। কিন্তু n = 10¹² (এক লক্ষ কোটি) হলে 10¹² বার — কয়েক ঘণ্টা লাগবে, interview-তে নিশ্চিত Time Limit Exceeded।

n = 10^12 হলে:
  brute O(n)   : 10^12 বার loop      -> অসম্ভব (ঘণ্টার হিসাব)
  smart O(√n)  : 10^6 বার loop       -> এক লহমা (~সেকেন্ডের ভগ্নাংশ)

কোথায় অপচয়? আমরা √n-এর ওপারের factor-গুলো (যেমন 36-এ 9, 12, 18, 36) আলাদা করে খুঁজছি — অথচ ওরা তো এপারের factor-দের (4, 3, 2, 1) জোড়া! একই তথ্য দু'বার খোঁজা। জোড়ার সম্পর্ক কাজে লাগালে অর্ধেকেরও কম কাজে শেষ।

9. Better thinking

মূল insight — √n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ (i আর n//i) গুনে নাও:

def count_factors(n):
    count = 0
    i = 1
    while i * i <= n:             # √n পর্যন্ত (i*i <= n, sqrt এড়িয়ে)
        if n % i == 0:
            count += 2            # i আর n//i — জোড়া
            if i * i == n:
                count -= 1        # perfect square: i আর n//i একই, একবার গোনো
        i += 1
    return count

লক্ষ করো i * i <= n লিখছি, i <= sqrt(n) নয় — কারণ i * i integer হিসাব, float-এর গোলমাল (sqrt-এর rounding) এড়ায়। প্রতিবার factor পেলে 2 যোগ (জোড়ার দুজন), কিন্তু i * i == n হলে (perfect square-এর মাঝবিন্দু) জোড়ার দুজন আসলে একই সংখ্যা — তাই 1 কমিয়ে দিই।

10. Thinking tweak

মূল মোচড় এক বাক্যে: factor জোড়ায় আসে, প্রতি জোড়ার ছোট জন ≤ √n — তাই √n পর্যন্ত খুঁজে প্রতিবার জোড়াসুদ্ধ গুনলেই সব factor, অর্ধেক কাজে।

ছোট্ট কিন্তু জরুরি tweak এর ভেতরে: perfect square-এ মাঝের factor (√n) নিজের জোড়া (36-এ 6×6 = 36) — তাকে দুবার গোনা যাবে না, একবার। এই −1 ভুলে গেলে perfect square-এ উত্তর ঠিক 1 বেশি আসবে।

এই "জোড়া ধরে √n পর্যন্ত" চিন্তা পরের problem-এর শিরদাঁড়া: prime check-এও আমরা একই যুক্তিতে √n পর্যন্তই ভাজক খুঁজব।

11. Step-by-step dry run

n = 36 দিয়ে smart version হাতে চালাই। i * i <= 36 মানে i যাবে 1..6 পর্যন্ত:

i	i*i	i*i <= 36?	36 % i == 0?	count বদল	perfect sq?	count (পরে)
1	1	হ্যাঁ	হ্যাঁ	+2	না	2
2	4	হ্যাঁ	হ্যাঁ	+2	না	4
3	9	হ্যাঁ	হ্যাঁ	+2	না	6
4	16	হ্যাঁ	হ্যাঁ	+2	না	8
5	25	হ্যাঁ	না (36%5=1)	0	—	8
6	36	হ্যাঁ	হ্যাঁ	+2	হ্যাঁ (−1)	9

i = 7-এ 49 > 36, loop থামল। count = 9 — ঠিক 9টা factor (1,2,3,4,6,9,12,18,36)। লক্ষ করো i = 6-এ +2 করে আবার −1 করলাম, কারণ 6 নিজের জোড়া (6×6=36)। এই −1 না করলে উত্তর ভুল করে 10 হতো।

12. Python solution

import math


def count_factors(n):
    """n-এর factor সংখ্যা — O(√n), জোড়া ধরে।"""
    if n < 1:
        return 0                  # positive n-এর জন্যই সংজ্ঞায়িত
    count = 0
    i = 1
    while i * i <= n:
        if n % i == 0:
            count += 2            # i আর n // i
            if i * i == n:
                count -= 1        # perfect square: মাঝের factor একবার
        i += 1
    return count


def count_factors_brute(n):
    """একই উত্তর, সরল O(n) — যাচাইয়ের জন্য।"""
    if n < 1:
        return 0
    return sum(1 for d in range(1, n + 1) if n % d == 0)


def list_factors(n):
    """বোনাস: factor গুলো sorted তালিকা হিসেবে।"""
    small, large = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
        i += 1
    return small + large[::-1]     # large উল্টে জুড়লে পুরো sorted


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_factors(12) == 6
assert count_factors(7) == 2          # prime -> ঠিক 2
assert count_factors(1) == 1          # শুধু নিজে
assert count_factors(36) == 9         # perfect square -> বিজোড়
assert count_factors(16) == 5         # perfect square
assert count_factors(100) == 9

# সরল আর চালাক — দুই পদ্ধতি সব ছোট n-এ মেলে কিনা
for n in range(1, 200):
    assert count_factors(n) == count_factors_brute(n)

assert list_factors(12) == [1, 2, 3, 4, 6, 12]
assert list_factors(36) == [1, 2, 3, 4, 6, 9, 12, 18, 36]
assert len(list_factors(36)) == count_factors(36)   # গোনা আর তালিকা মেলে

print(count_factors(12))    # 6
print(count_factors(36))    # 9
print(count_factors(7))     # 2
print("সব test pass!")

13. Line-by-line explanation

    if n < 1:
        return 0

factor গোনা positive সংখ্যার জন্যই অর্থপূর্ণ; 0 বা negative-এ 0 ফেরাই (রক্ষাকবচ)।

    while i * i <= n:

এই problem-এর প্রাণ। i চলে 1 থেকে √n পর্যন্ত — কিন্তু sqrt না ডেকে i * i <= n লিখছি, যাতে integer হিসাবেই থাকে আর float rounding-এর ভুল না হয়।

        if n % i == 0:
            count += 2

i ভাগ করলে (011-এর চেক), জোড়ার দুজন — i আর n // i — দুটোকেই গুনি, তাই +2।

            if i * i == n:
                count -= 1

সবচেয়ে ভোলা লাইন। perfect square-এ মাঝের factor (√n) নিজের জোড়া (6×6=36), তাই দুবার গোনা চলবে না — একবার কমিয়ে দিই।

def list_factors(n):
    ... small.append(i) ...  if i != n // i: large.append(n // i)
    return small + large[::-1]

বোনাস — ছোট factor-দের small-এ, বড়দের large-এ জমাই; i != n // i চেক perfect square-এ মাঝেরটা দুবার ঢোকা আটকায়। শেষে large[::-1] (উল্টানো) জুড়লে পুরো তালিকা sorted।

for n in range(1, 200) loop-টা চালাক version-কে সরল version-এর সাথে 199টা সংখ্যায় মিলিয়ে যাচাই করে — এই "সরল দিয়ে চালাক verify" এই level-এর সোনার নিয়ম। সব মিললে সব test pass!।

14. Output walkthrough

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

6
9
2
সব test pass!

তিনটা লাইন তিনটা print থেকে: count_factors(12) → 6, count_factors(36) → 9 (perfect square, বিজোড়), count_factors(7) → 2 (prime)। তার আগে সব assert — নির্দিষ্ট কেস, 1..199 জুড়ে দুই পদ্ধতির মিল, আর তালিকা-বনাম-গোনা — চুপচাপ pass করেছে। শেষ লাইন সব test pass! মানে O(√n) চালাক version সব ক্ষেত্রে সরল version-এর সমান উত্তর দেয়।

15. Time complexity

O(√n) — loop চলে 1 থেকে √n পর্যন্ত, তাই প্রায় √n বার। n = 10¹² হলেও মাত্র 10⁶ ধাপ — সেকেন্ডের ভগ্নাংশ। (brute version O(n) — n = 10¹²-এ অসম্ভব ধীর।) এই O(n) → O(√n) নামানোই এই level-এর কেন্দ্রীয় শিক্ষা।

16. Space complexity

• count_factors: O(1) — শুধু count, i; কোনো list নেই।
• list_factors: O(√n) (বা মোট factor সংখ্যার সমান) — কারণ factor-গুলো তালিকায় জমা হয়।

শুধু গুনতে হলে O(1) space-ই যথেষ্ট।

17. Common mistakes

1. perfect square-এ −1 ভুলে যাওয়া — এক নম্বর ফাঁদ। 36-এ 6 দুবার গোনা পড়লে উত্তর ভুল করে 10 হয়। if i * i == n: count -= 1 চাই।
2. i <= sqrt(n) দিয়ে float-ভুল — math.sqrt(n) float দেয়, বড় n-এ rounding-এ একটা factor ফসকাতে বা বাড়তে পারে। সবসময় i * i <= n (integer) লেখো।
3. range(1, n) দিয়ে n-কে বাদ — n নিজেও তো নিজের factor; brute-এ range(1, n+1) লাগে।
4. +2-এর বদলে +1 করা — √n পর্যন্ত খুঁজলে প্রতিবার জোড়া (i ও n//i) পাও, তাই +2; শুধু +1 করলে √n-এর ওপারের factor-গুলো বাদ পড়বে।
5. n = 1 ভুল হওয়া — i=1, 1*1<=1 সত্যি, 1%1==0 → +2, কিন্তু 1*1==1 → −1, মোট 1। ঠিক (1-এর factor শুধু নিজে)। কিন্তু hand-rolled version-এ সাবধান না হলে এটা গুলিয়ে যায়।

18. Harder problems that inherit this idea

• 013 — Check Prime (এই repo) — prime মানে ঠিক 2টা factor; এই √n loop-এ একটাও ভাজক পেলেই composite — সরাসরি পরের ধাপ।
• 024 — Number of Divisors (এই repo) — বড় সংখ্যায় factorization থেকে (e₁+1)(e₂+1)... সূত্রে divisor গোনা; এই √n গোনার গণিত-রূপ। সম্পর্কিত: CSES — Counting Divisors (https://cses.fi/problemset/task/1713)।
• LeetCode — Four Divisors (https://leetcode.com/problems/four-divisors/) — ঠিক 4টা divisor আছে এমন সংখ্যা খোঁজা; এই factor-জোড়া গোনার সরাসরি প্রয়োগ।

19. Pattern learned

√n factor-pair counting — factor জোড়ায় আসে, প্রতি জোড়ার ছোট জন ≤ √n, তাই √n পর্যন্ত খুঁজে জোড়াসুদ্ধ গুনলেই সব factor। বড় শিক্ষা: O(n) loop-কে O(√n)-এ নামানোর এই "জোড়ার অপর প্রান্ত n//i দিয়ে পাওয়া যায়" কৌশলটাই এই level-এর master key — prime check, factorization সব এর সন্তান। আর perfect square-এর মাঝবিন্দু একবার গোনার সতর্কতা।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "count factors = i*i <= n loop, প্রতি n%i==0-তে +2 (i ও n//i), কিন্তু i*i==n হলে −1 (perfect square-এর মাঝ একবার)। O(n) থেকে O(√n)-এ নামার মূল মন্ত্র: জোড়ার অপর প্রান্ত n//i আপনিই পাওয়া যায়। sqrt নয়, i*i দিয়ে compare।"

আগের ধাপ → 011 — Divisibility Rules (যে n % d == 0 চেক বারবার চালাচ্ছি)। পরের ধাপ → 013 — Check Prime (এই √n loop-এ একটাও ভাজক পেলেই composite)।

ফিরে দেখা: এই 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" হিসেবে লেখা।