046 — Count Triplets¶

জোড়া গোনা শিখেছ — এবার এক ধাপ উপরে: তিন জনের দল, triplet। সূত্র একই পরিবারের, শুধু C(n, 2)-এর জায়গায় C(n, 3) = n(n−1)(n−2)/6। কিন্তু আসল শেখাটা এখানে আরও গভীর: brute force-এ তিনটা nested loop মানে O(n³) — interview-তে সবচেয়ে কুখ্যাত ফাঁদ। কীভাবে গোনা না বানিয়েও সঠিক সংখ্যা পাওয়া যায়, সেই চোখটাই দামি।

Source¶

Original source: Classic exercise (triplet counting)
Platform: Classic exercise — https://discrete.openmathbooks.org/
Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
Difficulty: Medium
Pattern: C(n, 3) / grouping (triplet counting)
Basic idea inherited from: 045 — Count Pairs (জোড়া → তিনজনের দল)

1. Problem in simple words¶

দুটো রূপে আসে:

সরল রূপ: n টা জিনিস থেকে 3টা বেছে কত দল (triplet) বানানো যায়? (order matter করে না — {A,B,C} যেভাবেই লেখো, এক)। উত্তর C(n, 3)।
Array/grouping রূপ: কোনো array-তে একই মানের জিনিস থেকে কয়টা 3-জনের দল হয়? বা "কয়টা index-ত্রয়ী (i, j, k), i<j<k, কোনো শর্ত মানে"।

দুটোই এক চিন্তা — "তিন জনের দল গোনা"। array-তে একই মানের frequency f হলে সেই মানের triplet C(f, 3)।

2. What is the math idea?¶

মূল idea — C(n, 3) = n(n−1)(n−2)/6।

কেন? তিনজনকে সাজিয়ে বাছলে n × (n−1) × (n−2) (nPr, order সহ)। কিন্তু একই 3 জনকে 3! = 6 ভাবে সাজানো যায় — মানে প্রতিটা দল 6 বার গোনা হয়েছে! তাই 6 দিয়ে ভাগ:

C(n, 3) = n × (n − 1) × (n − 2) / 6

Array-এ একই মানের frequency f হলে সেই মানের triplet C(f, 3); মোট = সব মানের C(f, 3)-এর যোগ।

3. Which basic idea does this inherit from?¶

এটা 045 (Count Pairs)-এর ঠিক পরের ধাপ, আর দুটোই 041 (Combination Basic)-এর বিশেষ ক্ষেত্র (r = 2 বনাম r = 3)। প্যাটার্নটা একই থাকে, শুধু r বদলায়:

C(n, 2) = n(n−1)/2 — জোড়া, 2! দিয়ে ভাগ
C(n, 3) = n(n−1)(n−2)/6 — তিনজন, 3! দিয়ে ভাগ

মূল ধারাবাহিকতা: nPr করে তারপর r! দিয়ে ভাগ করে overcount মুছি (041-এর সেই শিক্ষা)। আর array রূপে 045-এর "frequency বের করে প্রতি দলে combination" কৌশলটাই এখানে C(f, 3)-এ চলে আসে।

4. Real-life analogy¶

ভাবো ক্লাসে n জন আছে, আর শিক্ষক 3 জনের project group বানাবেন (কোনো পদ নেই — শুধু "এই তিন জন একসাথে")।

প্রথম জন বাছার n উপায়, দ্বিতীয় n−1, তৃতীয় n−2 → n(n−1)(n−2)।
কিন্তু {রিমা, করিম, সোহা} group — তুমি যে ক্রমেই তিনজনের নাম ডাকো, group একটাই। তিনজনকে সাজানোর উপায় 3! = 6, মানে প্রতিটা group 6 বার গোনা হয়েছে!

তাই 6 দিয়ে ভাগ → C(n, 3)। 5 জন থাকলে 5×4×3/6 = 10টা আলাদা group। জোড়ার (2 দিয়ে ভাগ) থেকে এক ধাপ উপরে — তিনজন বলে এবার 6 দিয়ে।

5. Visual explanation¶

প্রথমে দেখো কেন 6 (=3!) দিয়ে ভাগ — একই দল কতবার গোনা হয় (দল {A,B,C}):

{A, B, C} দলকে সাজানোর 3! = 6 উপায়:
   ABC  ACB  BAC  BCA  CAB  CBA
   \_____________________________/
        সবই একই দল {A, B, C}

nPr (order সহ) প্রতিটা দল 6 বার গোনে
তাই C(n,3) = nPr / 6

এবার C(5,3)-এ formula কীভাবে কাজ করে:

        5 × 4 × 3      60
C(5,3) = ----------- = ----- = 10
          3 × 2 × 1      6

হাতে: {123,124,125,134,135,145,234,235,245,345} = 10 টা ✓

আর array grouping রূপ (frequency দিয়ে):

nums = [7, 7, 7, 7, 2]   (মান 7 আছে 4 বার)
মান 7 -> f=4 -> C(4,3) = 4 triplet
মান 2 -> f=1 -> C(1,3) = 0
                মোট = 4

6. Example input and output¶

সরল C(n, 3):
   n=5 -> 10       n=6 -> 20       n=2 -> 0       n=3 -> 1

array grouping (একই মানের triplet):
   [7,7,7,7,2]    ->  4    (মান 7: C(4,3)=4)
   [1,1,1,2,2,2]  ->  2    (1:C(3,3)=1, 2:C(3,3)=1)
   [1,2,3,4]      ->  0    (কোনো মান 3 বার নেই)

Edge case: n < 3 → 0 (3 জনের দল বানাতে অন্তত 3টা লাগে)। array-তে কোনো মান 3 বারের কম থাকলে সেই মানে 0 triplet।

7. Brute force thinking¶

সবচেয়ে সরাসরি — তিনটা nested loop-এ সব triplet গুনে ফেলা। সরল রূপে:

def count_triplets_brute(n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):   # i < j < k -> প্রতিটা দল একবার
                count += 1
    return count

array grouping-এও একই কাঠামো — তিন loop, i<j<k আর তিন মান সমান হলে গোনো। i<j<k রাখায় প্রতিটা দল ঠিক একবার গোনা হয় — একদম ঠিক উত্তর, আর formula verify করার নিখুঁত উপায়।

8. Why brute force may be slow¶

তিনটা nested loop মানে O(n³) — সবচেয়ে কুখ্যাত interview-ফাঁদ:

n = 1000 হলে:
  triple loop: প্রায় n³/6 ≈ 1.6×10^8 ধাপ -> সীমার কাছে, ঝুঁকি
n = 100000 হলে:
  triple loop: ~10^14 ধাপ -> সম্পূর্ণ অসম্ভব
  formula:     n(n−1)(n−2)/6 -> 2 গুণ, 1 ভাগ -> O(1)!

triplet-এর সংখ্যা O(n³) হলেও, সংখ্যাটা জানতে O(n³) লাগে না — formula এক ধাপে দেয়।

9. Better thinking¶

মূল insight: triplet একে একে না গুনে সরাসরি n(n−1)(n−2)/6:

def count_triplets(n):
    if n < 3:
        return 0
    return n * (n - 1) * (n - 2) // 6

array grouping-এ: একই মান ছাড়া (এই রূপে) দল হয় না, তাই frequency গোনো (এক pass), প্রতি মানে C(f, 3) যোগ করো — O(n)-এ:

from collections import Counter

def triplets_same_value(nums):
    freq = Counter(nums)
    return sum(f * (f - 1) * (f - 2) // 6 for f in freq.values())

(আরও সাধারণ "i<j<k শর্ত মানে কয়টা" সমস্যায় প্রায়ই middle element fix করে দুপাশ গোনা হয় — কিন্তু সেটা পরের level-এর কৌশল; এখানে মূল চিন্তা C(n,3) চেনা।)

10. Thinking tweak¶

আসল "আহা" মুহূর্ত: তিনটা nested loop দেখলেই থামো — "তিন জনের দল গোনা" প্রায়ই একটা C(n, 3) বা frequency-যোগ, O(n³) নয়।

আর সাধারণ নিয়মটা গেঁথে নাও: r জনের দল = nPr / r! — প্রতিটা দল r! বার গোনা হয়, তাই r! দিয়ে ভাগ। জোড়ায় 2, তিনজনে 6, চারজনে 24। "overcount করে তারপর r! দিয়ে শোধরাও" — এই এক চিন্তা সব দল-গোনায় খাটে।

11. Step-by-step dry run¶

চলো array grouping nums = [5, 5, 5, 5] চালাই — মান 5 আছে 4 বার, formula C(4, 3) = 4×3×2//6 = 4।

ধাপ	কাজ	অবস্থা
1	frequency গোনা	মান 5 → 4 বার
2	C(4, 3)	4×3×2 = 24, //6 = 4
3	যোগ	4

হাতে যাচাই — index ত্রয়ী (i<j<k) যেখানে তিন মানই সমান: (0,1,2), (0,1,3), (0,2,3), (1,2,3) — ঠিক 4টা ✓।

12. Python solution¶

from collections import Counter


def count_triplets(n):
    """C(n, 3): n জিনিস থেকে কয়টা 3-জনের দল = n(n-1)(n-2)/6।"""
    if n < 3:
        return 0
    return n * (n - 1) * (n - 2) // 6


def triplets_same_value(nums):
    """একই মানের কয়টা triplet: প্রতি মানে C(f, 3)-এর যোগ।"""
    freq = Counter(nums)
    return sum(f * (f - 1) * (f - 2) // 6 for f in freq.values())


# --- brute force verifier (সব triplet একে একে গুনে) ---
def count_triplets_brute(n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                count += 1
    return count


def triplets_same_brute(nums):
    count = 0
    m = len(nums)
    for i in range(m):
        for j in range(i + 1, m):
            for k in range(j + 1, m):
                if nums[i] == nums[j] == nums[k]:
                    count += 1
    return count


# --- ছোট test গুলো (সব pass করা উচিত) ---
import math

# C(n, 3) সঠিক কিনা
assert count_triplets(5) == 10
assert count_triplets(6) == 20
assert count_triplets(3) == 1
assert count_triplets(2) == 0
assert count_triplets(0) == 0

# math.comb + brute-এর সাথে cross-check
for n in range(0, 25):
    assert count_triplets(n) == (math.comb(n, 3) if n >= 3 else 0)
    assert count_triplets(n) == count_triplets_brute(n)

# array grouping == brute (নানা array)
tests = [
    [7, 7, 7, 7, 2],
    [1, 1, 1, 2, 2, 2],
    [1, 2, 3, 4],
    [],
    [5, 5],
    [9, 9, 9, 9, 9],
]
for arr in tests:
    assert triplets_same_value(arr) == triplets_same_brute(arr)

assert triplets_same_value([7, 7, 7, 7, 2]) == 4
assert triplets_same_value([1, 1, 1, 2, 2, 2]) == 2
assert triplets_same_value([1, 2, 3, 4]) == 0

print(count_triplets(5))                        # 10
print(triplets_same_value([7, 7, 7, 7, 2]))     # 4
print(triplets_same_value([1, 1, 1, 2, 2, 2]))  # 2
print("সব test pass!")

13. Line-by-line explanation¶

def count_triplets(n):
    if n < 3:
        return 0
    return n * (n - 1) * (n - 2) // 6

3 জনের দল বানাতে অন্তত 3টা লাগে, তাই n<3 হলে 0। নাহলে n(n−1)(n−2)/6 — পরপর তিন সংখ্যার গুণ সবসময় 6 দিয়ে নিঃশেষে ভাগ যায়, তাই // নিরাপদ।

def triplets_same_value(nums):
    freq = Counter(nums)
    return sum(f * (f - 1) * (f - 2) // 6 for f in freq.values())

Counter এক pass-এ frequency গোনে; তারপর প্রতিটা মানের জন্য C(f, 3) যোগ করি — একই মানের ভেতরের triplet।

def count_triplets_brute(n):
    for i ...: for j ...: for k in range(j+1, n): count += 1

verify-র brute — সব i<j<k ত্রয়ী গুনে। O(n³), ধীর কিন্তু নিশ্চিত, তাই formula মেলাতে কাজে লাগে।

বাকি assert লাইনগুলো math.comb আর brute force — দুই পথে যাচাই করছে। সব মিললে শেষে সব test pass!।

14. Output walkthrough¶

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

10
4
2
সব test pass!

প্রথম: count_triplets(5) = 10 (5×4×3/6)। দ্বিতীয়: triplets_same_value([7,7,7,7,2]) = 4 (মান 7 → C(4,3)=4)। তৃতীয়: [1,1,1,2,2,2] = 2 (দুই মানই C(3,3)=1)। আগের সব assert (math.comb ও brute force) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity¶

count_triplets(n) O(1) — দুটো গুণ, একটা ভাগ। triplets_same_value(nums) O(n) — frequency এক pass, তারপর distinct মানের উপর যোগ। brute force-এর O(n³) থেকে নাটকীয় উন্নতি।

16. Space complexity¶

count_triplets O(1)। triplets_same_value O(d) যেখানে d = distinct মানের সংখ্যা (Counter-এ) — খারাপ ক্ষেত্রে O(n)।

17. Common mistakes¶

6 (=3!) দিয়ে ভাগ ভুলে যাওয়া — n(n−1)(n−2) দিলে প্রতিটা দল 6 বার গোনা; /6 লাগবেই।
2 দিয়ে ভাগ করে ফেলা (জোড়ার অভ্যাসে) — triplet-এ 3! = 6, জোড়ার 2 নয়।
O(n³) brute force রেখে দেওয়া — বড় n-এ অসম্ভব; formula বা frequency-যোগ নাও।
n < 3-এ ভুল — 3টার কম জিনিসে কোনো triplet নেই (formula এক্ষেত্রেও 0, তবু সাবধান)।
array-তে "একই মান" আর "যেকোনো i<j<k" গুলিয়ে ফেলা — এই note একই-মান triplet গোনে; সাধারণ শর্তযুক্ত triplet আলাদা কৌশল চায়।

18. Harder problems that inherit this idea¶

LeetCode — Number of Arithmetic Triplets (https://leetcode.com/problems/number-of-arithmetic-triplets/) — শর্তযুক্ত triplet গোনা।
LeetCode — 3Sum (https://leetcode.com/problems/3sum/) — triplet খোঁজা (গোনার চেয়ে কঠিন, two-pointer)।
045 — Count Pairs (এই repo) — এর জোড়া-রূপ; দুটো একসাথে দেখলে r-এর সাধারণ প্যাটার্ন বোঝা যায়।

19. Pattern learned¶

Triplet counting via C(n,3) = n(n−1)(n−2)/6 — তিন জনের দল = nPr / 3!; array-তে frequency বের করে Σ C(f, 3)। সাধারণ নিয়ম: r জনের দল = nPr / r!। মূল signal: তিন nested loop দেখলেই থামো — এটা C(n,3) বা frequency-যোগ হতে পারে।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "কয়টা triplet = C(n,3) = n(n−1)(n−2)/6 (3! দিয়ে ভাগ); array-তে Σ C(f,3)। সাধারণ নিয়ম nPr/r! — O(n³) loop দেখলেই formula খোঁজো।"

পরের ধাপ → 047 — Count Subsets (এবার দল নয়, সব উপসেট — প্রতিটার হ্যাঁ/না, 2^n)।

ফিরে দেখা: আগের ধাপ → 045 — Count Pairs · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

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