Problem link ও উৎস
- **Original source:** Classic hash set / math exercise
- **Platform:** LeetCode —
- **Topic:** hash set
- **Difficulty:** Easy
- **Pattern:** seen-set
- **Basic idea inherited from:** seen-set; sum formula দিয়েও solve করা যায় ([../../01-math-based-programming-fundamentals/](../../01-math-based-programming-fundamentals/README.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`0` থেকে `n` পর্যন্ত `n+1`টা সংখ্যার মধ্য থেকে ঠিক **একটা** বাদ দিয়ে বাকি `n`টা সংখ্যা একটা array `nums`-এ এলোমেলো করে দেওয়া আছে। তোমাকে বের করতে হবে — কোন সংখ্যাটা **নেই**?
```text
nums = [3, 0, 1] → 2 (0..3 থেকে 2 বাদ)
nums = [0, 1] → 2 (0..2 থেকে 2 বাদ)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [3, 0, 1] Output: 2
Input : [0, 1] Output: 2
Input : [9,6,4,2,3,5,7,0,1] Output: 8
Edge : [0] Output: 1 (0..1 থেকে 1 বাদ)
Edge : [1] Output: 0 (0..1 থেকে 0 বাদ)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ক্লাসে roll number 0 থেকে n পর্যন্ত। আজ একজন অনুপস্থিত। তুমি উপস্থিত সবার roll একটা খাতায় (set) টুকে নিলে, তারপর 0 থেকে গুনে গুনে দেখলে কোন roll-টা খাতায় নেই — সেই ছাত্রই অনুপস্থিত। অথবা চালাকি: সব roll-এর মোট যোগফল আগেই জানা; উপস্থিতদের যোগফল বিয়োগ করলেই অনুপস্থিতের roll।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত। এক, **seen-set** (Pattern 4): সব সংখ্যা একটা set-এ তুলে নিয়ে `0..n`-এর মধ্যে কোনটা set-এ নেই সেটা খুঁজি। দুই, একটা **সুন্দর গাণিতিক বিকল্প** — sum formula ([../../01-math-based-programming-fundamentals/](../../01-math-based-programming-fundamentals/README.md)): `0..n`-এর পূর্ণ যোগফল থেকে array-র যোগফল বিয়োগ করলেই বাদ পড়া সংখ্যা বেরিয়ে আসে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
Set version-এ logic: পূর্ণ range `0..n`-এর প্রতিটা সংখ্যা থাকার কথা; যেটা set-এ নেই, সেটাই missing। Math version-এ logic: `0 + 1 + ... + n = n*(n+1)/2` (Gauss-এর যোগফল সূত্র)। তাই `missing = n*(n+1)/2 - sum(nums)` — পূর্ণ যোগফল আর আসল যোগফলের পার্থক্যই হারানো সংখ্যা।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
Hashing approach-এ একটা **hash set** (Python-এ `set`) — দ্রুত "এই সংখ্যা আছে কি না" membership-এর জন্য। (Math approach-এ কোনো data structure লাগে না, শুধু দুটো যোগফল।)
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Set-এ `candidate in seen` membership গড়ে **O(1)**। তাই array-কে একবার set-এ তুলে `0..n` scan করলে প্রতিটা check instant — মোট O(n)। List হলে প্রতিটা check O(n) হয়ে মোট O(n^2) হতো; set সেটা ঠেকায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `0` থেকে `n` পর্যন্ত প্রতিটা সংখ্যার জন্য পুরো array খুঁজে দেখি সেটা আছে কি না; যেটা পাই না, সেটাই missing।
```text
candidate 0..n-এর প্রতিটার জন্য:
candidate কি nums-এ আছে? (পুরো array scan)
না থাকলে → return candidate
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা candidate-এর জন্য পুরো array scan = মোট **O(n^2)**। অথচ array-কে একবার set-এ তুলে নিলে প্রতিটা membership-check O(1) হয়ে মোট O(n)। বারবার পুরো array খোঁজাটাই এখানে অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পূর্ণ range আমরা জানি (`0..n`)** — তাই হয় (set দিয়ে) "কে নেই" সরাসরি খুঁজি, নয়তো (math দিয়ে) জানা পূর্ণ যোগফল থেকে আসল যোগফল বিয়োগ করি। দুই পথই range জানার সুবিধা নেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Seen-set: array-কে set-এ তোলো, তারপর `0` থেকে `n` পর্যন্ত প্রথম যে সংখ্যা set-এ নেই সেটা ফেরত দাও। Math: `n*(n+1)//2 - sum(nums)` — এক লাইনে, O(1) extra space। দুটোই O(n) time; set version বেশি general (negative/অসংলগ্ন value-তেও খাটে), math version বেশি মিতব্যয়ী।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোনটা নেই খুঁজি" প্রশ্নটাকে seen-set দিয়ে "কোনটা set-এ নেই" করে ফেলো — অতীত মনে রেখে absence ধরা। আর গাণিতিক মোচড়: পুরোটা না খুঁজে শুধু *যোগফলের পার্থক্য* দেখো।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [3, 0, 1]`, এখানে `n = len(nums) = 3`, তাই পূর্ণ range `0..3`:
```text
seen = {3, 0, 1}
candidate 0? 0 in seen → আছে
candidate 1? 1 in seen → আছে
candidate 2? 2 in seen → নেই! return 2
```
Math দিয়ে cross-check:
```text
পূর্ণ যোগফল = 3*4/2 = 6
array যোগফল = 3+0+1 = 4
missing = 6 - 4 = 2 ✓
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums = [0, 1]` (এখানে `n = 2`, range `0..2`):
1. `seen = {0, 1}`।
2. `candidate = 0`: `0 in seen?` হ্যাঁ → এগোও।
3. `candidate = 1`: `1 in seen?` হ্যাঁ → এগোও।
4. `candidate = 2`: `2 in seen?` না → return `2`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def missing_number(nums):
seen = set(nums) # সব সংখ্যা স্মৃতিতে
n = len(nums)
for candidate in range(n + 1): # পূর্ণ range 0..n
if candidate not in seen: # কোনটা নেই?
return candidate
return -1 # valid input-এ পৌঁছায় না
def missing_number_math(nums): # বিকল্প: sum formula, O(1) space
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
# ---- tests ----
assert missing_number([3, 0, 1]) == 2
assert missing_number([0, 1]) == 2
assert missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
assert missing_number([0]) == 1
assert missing_number([1]) == 0
# দুই approach একই উত্তর দেয়
assert missing_number_math([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
assert missing_number_math([0]) == 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `seen = set(nums)` — পুরো array-কে set-এ তুলি, যাতে membership O(1)।
- `n = len(nums)` — array-তে `n`টা সংখ্যা, তাই পূর্ণ range `0..n`।
- `for candidate in range(n + 1)` — `0` থেকে `n` পর্যন্ত প্রতিটা সম্ভাব্য সংখ্যা।
- `if candidate not in seen` — এটা কি array থেকে বাদ পড়েছে?
- `return candidate` — প্রথম যেটা নেই, সেটাই missing।
- `missing_number_math` — Gauss-এর সূত্রে পূর্ণ যোগফল `n*(n+1)//2` থেকে array-র যোগফল বিয়োগ; integer division `//` ঠিক মান দেয়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[3,0,1]`: `seen={0,1,3}`, `candidate=2` set-এ নেই → `2`। `[0,1]`: 2 missing → `2`। বড় array-তে 8 missing → `8`। `[0]`: range `0..1`, 1 নেই → `1`। `[1]`: 0 নেই → `0`। math version-ও একই উত্তর দেয়। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
দুই অস্ত্র — seen-set (general) আর Gauss sum formula (O(1) space)।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// missing number from 0..n (seen-set)
function missingNumber(nums) {
const seen = new Set(nums);
for (let c = 0; c <= nums.length; c++) { // পূর্ণ range 0..n
if (!seen.has(c)) return c;
}
return -1; // valid input-এ পৌঁছায় না
}
// বিকল্প: sum formula, O(1) extra space
function missingNumberMath(nums) {
const n = nums.length;
const total = (n * (n + 1)) / 2; // 0+1+...+n
return total - nums.reduce((a, b) => a + b, 0);
}
// ---- test cases (example + edge) ----
assert(missingNumber([3, 0, 1]) === 2, "basic");
assert(missingNumber([0, 1]) === 2, "small");
assert(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]) === 8, "big");
assert(missingNumber([0]) === 1, "edge-1"); // edge
assert(missingNumber([1]) === 0, "edge-0"); // edge
assert(missingNumberMath([9, 6, 4, 2, 3, 5, 7, 0, 1]) === 8, "math-big");
assert(missingNumberMath([0]) === 1, "math-edge");
console.log("সব JS test pass!");
```
> **JS টীকা:** array যোগফল `nums.reduce((a, b) => a + b, 0)` — initial value `0` দাও যাতে খালি array-তেও কাজ করে। `(n * (n + 1)) / 2` JS-এ float division কিন্তু সবসময় integer-এ মেলে (পরপর দুই সংখ্যার গুণ even)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function missingNumber(nums: number[]): number {
const seen: Set