045 — Count Pairs¶

nCr-এর সবচেয়ে কাজের ছোট রূপ — C(n, 2)। "কয়টা জোড়া বানানো যায়?" এই প্রশ্ন interview-তে অগুনতিবার আসে: handshake, good pairs, equal elements — সবেতেই। সূত্রটা এক লাইনের (n(n−1)/2), কিন্তু আসল শক্তি হলো একে চিনতে পারা — কখন একটা গোনার সমস্যা আসলে "জোড়া গোনা"। সেই চোখটাই এখানে বানাব।

Source¶

Original source: LeetCode Number of Good Pairs
Platform: LeetCode — https://leetcode.com/problems/number-of-good-pairs/
Topic: Math-based programming fundamentals → Level 3: Counting & Combinatorics
Difficulty: Easy
Pattern: C(n, 2) (pair counting)
Basic idea inherited from: 041 — Combination Basic (r = 2-এর বিশেষ ক্ষেত্র)

1. Problem in simple words¶

দুটো রূপে আসে এই problem:

সরল রূপ: n টা জিনিস থেকে 2টা বেছে কত জোড়া বানানো যায়? (order matter করে না — {A,B} আর {B,A} একই)। উত্তর C(n, 2)।
Array রূপ (good pairs): একটা array দেওয়া; কয়টা index-জোড়া (i, j) আছে যেখানে i < j আর nums[i] == nums[j] (মান সমান)?

দুটোই আসলে এক চিন্তা — "জোড়া গোনা"। array রূপে: একই মানের জিনিসগুলোকে দল করো, প্রতি দলে আবার C(দলের আকার, 2) জোড়া।

2. What is the math idea?¶

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

কেন? প্রথম জনকে বাছার n উপায়, দ্বিতীয় জনকে n−1 উপায় → n(n−1)। কিন্তু (A তারপর B) আর (B তারপর A) একই জোড়া — প্রতিটা জোড়া 2 বার গোনা হলো, তাই 2 দিয়ে ভাগ:

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

Array-এ একই মানের frequency যদি f হয়, সেই মানের জোড়া C(f, 2); মোট = সব মানের C(f, 2)-এর যোগ।

3. Which basic idea does this inherit from?¶

এটা 041 (Combination Basic)-এর সবচেয়ে ব্যবহৃত বিশেষ ক্ষেত্র — r = 2। 041-এর সাধারণ C(n, r) = nPr/r!-এ r = 2 বসালেই n(n−1)/2।

কেন আলাদা note? কারণ "জোড়া গোনা" এত ঘন ঘন আসে যে এর pattern আলাদা করে চেনা জরুরি। আর array রূপটা একটা নতুন কৌশল যোগ করে: গোনার আগে দল ভাগ করো (group by value), তারপর প্রতি দলে combination। এই "frequency বের করে তারপর C(f,2)" idea পরে hashing/counting problem-এ বারবার লাগবে।

4. Real-life analogy¶

ভাবো একটা পার্টিতে n জন এসেছে, আর সবাই সবার সাথে একবার করে handshake করবে। মোট কয়টা handshake হবে?

প্রথম হাত বাড়াতে পারে n জনের যে কেউ → n
তার সাথে মেলাতে পারে বাকি n−1 জন → n−1
কিন্তু রিমা-করিম handshake আর করিম-রিমা handshake — একই ঘটনা! দুবার গোনা হলো।

তাই মোট = n(n−1)/2। 5 জন থাকলে 5×4/2 = 10টা handshake। এই "প্রত্যেকে প্রত্যেকের সাথে একবার, কিন্তু জোড়া দুবার গোনা যায়" — এটাই C(n, 2)-এর প্রাণ।

5. Visual explanation¶

প্রথমে দেখো handshake-এ কেন 2 দিয়ে ভাগ (4 জন):

4 জন: A B C D — সব জোড়া:

   A-B   A-C   A-D
         B-C   B-D
               C-D
   মোট 6 টা জোড়া = C(4,2) = 4×3/2 = 6 ✓

grid-এ দেখলে (× = জোড়া, উপরের ত্রিভুজ মাত্র):
      A  B  C  D
   A  .  ×  ×  ×
   B  .  .  ×  ×
   C  .  .  .  ×
   D  .  .  .  .
   diagonal-এর উপরের অর্ধেক = n(n−1)/2

এবার array রূপ — frequency দিয়ে দল ভাগ (good pairs):

nums = [1, 2, 1, 3, 1]   (মান 1 আছে 3 বার, 2 আছে 1, 3 আছে 1)

মান 1 -> f=3 -> C(3,2)=3 জোড়া: (0,2)(0,4)(2,4)
মান 2 -> f=1 -> C(1,2)=0
মান 3 -> f=1 -> C(1,2)=0
                মোট good pairs = 3

লক্ষ করো — একই মান ছাড়া জোড়া হয় না, তাই প্রতি মানের ভেতরেই C(f, 2)।

6. Example input and output¶

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

good pairs (array):
   [1,2,3,1,1,3]  ->  4    (মান 1: C(3,2)=3, মান 3: C(2,2)=1)
   [1,1,1,1]      ->  6    (C(4,2)=6)
   [1,2,3]        ->  0    (কোনো মান repeat নেই)

Edge case: n = 0 বা n = 1 → 0 জোড়া (জোড়া বানাতে অন্তত 2টা লাগে)। array-তে সব মান আলাদা হলে good pairs = 0।

7. Brute force thinking¶

সবচেয়ে সরাসরি — সব জোড়া nested loop-এ গুনে ফেলা। সরল রূপে:

def count_pairs_brute(n):
    count = 0
    for i in range(n):
        for j in range(i + 1, n):   # i < j -> প্রতিটা জোড়া একবার
            count += 1
    return count

array-এর good pairs-এও একই — দুটো loop, i < j আর nums[i] == nums[j] হলে গোনো:

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

i < j রাখায় প্রতিটা জোড়া ঠিক একবার গোনা হয় — একদম ঠিক উত্তর, আর formula verify করার নিখুঁত উপায়।

8. Why brute force may be slow¶

দুটো nested loop মানে O(n²) — সব জোড়া একে একে ছোঁয়া:

n = 100000 হলে:
  nested loop: প্রায় n²/2 = 5×10^9 ধাপ -> Time Limit Exceeded
  formula:     n(n−1)/2 -> একটা গুণ, একটা ভাগ -> O(1)!

জোড়ার সংখ্যাটা O(n²), কিন্তু সংখ্যাটা জানতে O(n²) লাগে না — formula এক ধাপে দেয়। array good pairs-এও frequency দিয়ে O(n)-এ নামানো যায় (নিচে)।

9. Better thinking¶

মূল insight: জোড়া একে একে না গুনে সরাসরি n(n−1)/2 ব্যবহার করো:

def count_pairs(n):
    return n * (n - 1) // 2

array good pairs-এ insight: একই মান ছাড়া জোড়া হয় না, তাই frequency গোনো (এক pass), তারপর প্রতি মানে C(f, 2) যোগ করো — সব O(n)-এ:

from collections import Counter

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

আরও সুন্দর running-trick: array ঘুরতে ঘুরতে প্রতিটা নতুন x-এর জন্য, আগে কতবার x দেখেছি সেটাই নতুন জোড়া — তারপর count বাড়াও। দুটোই O(n)।

10. Thinking tweak¶

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

আর array রূপে দ্বিতীয় tweak: জোড়া বানাতে দুই জিনিসকে সমান হতে হলে আগে দল ভাগ করো — একই মানের কতগুলো (frequency), তারপর প্রতি দলে C(f, 2)। "গোনার আগে group, তারপর প্রতি group-এ combination" — এই অভ্যাসটা hashing-যুগের অসংখ্য counting problem-এর চাবি।

11. Step-by-step dry run¶

চলো good pairs nums = [1, 2, 1, 1] চালাই (frequency পথ):

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

মানে 3টা good pair।

হাতে যাচাই — index জোড়া যেখানে মান সমান: (0,2), (0,3), (2,3) — সবগুলোতেই মান 1, ঠিক 3টা ✓।

12. Python solution¶

from collections import Counter


def count_pairs(n):
    """C(n, 2): n জিনিস থেকে কয়টা জোড়া = n(n-1)/2।"""
    if n < 2:
        return 0
    return n * (n - 1) // 2


def good_pairs(nums):
    """কয়টা (i, j), i<j, nums[i]==nums[j]: প্রতি মানে C(f, 2)-এর যোগ।"""
    freq = Counter(nums)
    return sum(f * (f - 1) // 2 for f in freq.values())


# --- brute force verifier (সব জোড়া একে একে গুনে) ---
def count_pairs_brute(n):
    return sum(1 for i in range(n) for j in range(i + 1, n))


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


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

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

# math.comb + brute-এর সাথে cross-check
for n in range(0, 30):
    assert count_pairs(n) == (math.comb(n, 2) if n >= 2 else 0)
    assert count_pairs(n) == count_pairs_brute(n)

# good pairs == brute (নানা array)
tests = [
    [1, 2, 3, 1, 1, 3],
    [1, 1, 1, 1],
    [1, 2, 3],
    [],
    [5],
    [2, 2, 3, 3, 3, 2],
]
for arr in tests:
    assert good_pairs(arr) == good_pairs_brute(arr)

assert good_pairs([1, 2, 3, 1, 1, 3]) == 4
assert good_pairs([1, 1, 1, 1]) == 6
assert good_pairs([1, 2, 3]) == 0

print(count_pairs(5))                       # 10
print(good_pairs([1, 2, 3, 1, 1, 3]))       # 4
print(good_pairs([1, 1, 1, 1]))             # 6
print("সব test pass!")

13. Line-by-line explanation¶

def count_pairs(n):
    if n < 2:
        return 0
    return n * (n - 1) // 2

জোড়া বানাতে অন্তত 2টা লাগে, তাই n<2 হলে 0। নাহলে n(n−1)/2 — integer division // কারণ n(n−1) সবসময় জোড় (পরপর দুই সংখ্যার একটা জোড়)।

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

Counter এক pass-এ প্রতিটা মান কতবার আছে গোনে; তারপর প্রতিটা frequency-র জন্য C(f, 2) যোগ করি — একই মানের ভেতরের জোড়া।

def good_pairs_brute(nums):
    for i ...: for j in range(i+1, ...):
        if nums[i] == nums[j]: count += 1

verify-র brute — সব i < j জোড়া দেখে মান সমান হলে গোনে। ধীর কিন্তু নিশ্চিত, তাই formula মেলাতে কাজে লাগে।

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

14. Output walkthrough¶

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

10
4
6
সব test pass!

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

15. Time complexity¶

count_pairs(n) O(1) — একটা গুণ-ভাগ। good_pairs(nums) O(n) — frequency গোনা এক pass, তারপর distinct মানের উপর যোগ। brute force-এর O(n²) থেকে বড় উন্নতি।

16. Space complexity¶

count_pairs O(1)। good_pairs O(d) যেখানে d = distinct মানের সংখ্যা (Counter-এ রাখা) — সবচেয়ে খারাপ ক্ষেত্রে O(n)।

17. Common mistakes¶

2 দিয়ে ভাগ ভুলে যাওয়া — n(n−1) দিলে প্রতিটা জোড়া দুবার গোনা; /2 লাগবেই।
n < 2-এ ভুল — 0 বা 1 জিনিসে কোনো জোড়া নেই; formula n(n−1)/2 এক্ষেত্রেও 0 দেয়, তবু খেয়াল রাখো।
good pairs-এ nested loop ব্যবহার — বড় array-তে O(n²); frequency দিয়ে O(n)-এ নামাও।
i < j শর্ত ভুলে jোড়া দুবার গোনা — brute-এ j শুরু i+1 থেকে, নাহলে (i,j) আর (j,i) দুবার।
float division ব্যবহার — / দিলে float; integer চাইলে // (আর n(n−1) সবসময় জোড়, তাই নিরাপদ)।

18. Harder problems that inherit this idea¶

LeetCode — Number of Good Pairs (https://leetcode.com/problems/number-of-good-pairs/) — হুবহু frequency → C(f, 2)।
046 — Count Triplets (এই repo) — একই চিন্তা, কিন্তু C(n, 3)।
LeetCode — Count Number of Pairs With Absolute Difference K (https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/) — hashmap + pair counting।

19. Pattern learned¶

Pair counting via C(n,2) = n(n−1)/2 — "প্রত্যেকে প্রত্যেকের সাথে / কয়টা জোড়া" দেখলেই এটা; array-তে আগে frequency, তারপর প্রতি দলে C(f, 2)-এর যোগ। মূল signal: handshake / equal pair / "কয়টা (i,j)" — সবই জোড়া গোনা।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "কয়টা জোড়া = C(n,2) = n(n−1)/2; array-তে frequency বের করে Σ C(f,2)। 'প্রত্যেকে প্রত্যেকের সাথে' দেখলেই জোড়া গোনা, nested loop নয়।"

পরের ধাপ → 046 — Count Triplets (একই চিন্তা, এবার তিন জনের দল — C(n,3))।

ফিরে দেখা: আগের ধাপ → 041 — Combination Basic · এই 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"।