Problem link ও উৎস
- **Original source:** LeetCode Number of Good Pairs
- **Platform:** LeetCode —
- **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-এর বিশেষ ক্ষেত্র)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো রূপে আসে এই problem:
1. **সরল রূপ:** n টা জিনিস থেকে 2টা বেছে কত জোড়া বানানো যায়? (order matter করে না — {A,B} আর {B,A} একই)। উত্তর `C(n, 2)`।
2. **Array রূপ (good pairs):** একটা array দেওয়া; কয়টা index-জোড়া `(i, j)` আছে যেখানে `i < j` আর `nums[i] == nums[j]` (মান সমান)?
দুটোই আসলে এক চিন্তা — "জোড়া গোনা"। array রূপে: একই মানের জিনিসগুলোকে দল করো, প্রতি দলে আবার `C(দলের আকার, 2)` জোড়া।
### Input ও output {#6-example-input-and-output}
```text
সরল 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।
### চেনা উদাহরণে বোঝা {#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)`-এর প্রাণ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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-এ বারবার লাগবে।
### ভেতরের অঙ্ক {#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 দিয়ে ভাগ:
```text
C(n, 2) = n × (n − 1) / 2
```
Array-এ একই মানের frequency যদি `f` হয়, সেই মানের জোড়া `C(f, 2)`; মোট = সব মানের `C(f, 2)`-এর যোগ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি — **সব জোড়া nested loop-এ গুনে ফেলা।** সরল রূপে:
```python
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]` হলে গোনো:
```python
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²)** — সব জোড়া একে একে ছোঁয়া:
```text
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`** ব্যবহার করো:
```python
def count_pairs(n):
return n * (n - 1) // 2
```
array good pairs-এ insight: একই মান ছাড়া জোড়া হয় না, তাই **frequency গোনো (এক pass), তারপর প্রতি মানে `C(f, 2)` যোগ করো** — সব O(n)-এ:
```python
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-এর চাবি।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো handshake-এ কেন 2 দিয়ে ভাগ (4 জন):
```text
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):
```text
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)`।
### ছোট input-এ ধাপে ধাপে {#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টা ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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