007 — Missing Number¶

Source¶

Original source: Classic hash set / math exercise
Platform: LeetCode — https://leetcode.com/problems/missing-number/
Topic: hash set
Difficulty: Easy
Pattern: seen-set
Basic idea inherited from: seen-set; sum formula দিয়েও solve করা যায় (../../01-math-based-programming-fundamentals/)

1. Problem in simple words¶

0 থেকে n পর্যন্ত n+1টা সংখ্যার মধ্য থেকে ঠিক একটা বাদ দিয়ে বাকি nটা সংখ্যা একটা array nums-এ এলোমেলো করে দেওয়া আছে। তোমাকে বের করতে হবে — কোন সংখ্যাটা নেই?

nums = [3, 0, 1]  →  2   (0..3 থেকে 2 বাদ)
nums = [0, 1]     →  2   (0..2 থেকে 2 বাদ)

2. Which basic idea does this inherit from?¶

দুটো ভিত। এক, seen-set (Pattern 4): সব সংখ্যা একটা set-এ তুলে নিয়ে 0..n-এর মধ্যে কোনটা set-এ নেই সেটা খুঁজি। দুই, একটা সুন্দর গাণিতিক বিকল্প — sum formula (../../01-math-based-programming-fundamentals/): 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 সেটা ঠেকায়।

6. Real-life analogy¶

ক্লাসে roll number 0 থেকে n পর্যন্ত। আজ একজন অনুপস্থিত। তুমি উপস্থিত সবার roll একটা খাতায় (set) টুকে নিলে, তারপর 0 থেকে গুনে গুনে দেখলে কোন roll-টা খাতায় নেই — সেই ছাত্রই অনুপস্থিত। অথবা চালাকি: সব roll-এর মোট যোগফল আগেই জানা; উপস্থিতদের যোগফল বিয়োগ করলেই অনুপস্থিতের roll।

7. Visual explanation¶

nums = [3, 0, 1], এখানে n = len(nums) = 3, তাই পূর্ণ range 0..3:

seen = {3, 0, 1}

candidate 0?  0 in seen → আছে
candidate 1?  1 in seen → আছে
candidate 2?  2 in seen → নেই!  return 2

Math দিয়ে cross-check:

পূর্ণ যোগফল = 3*4/2 = 6
array যোগফল = 3+0+1 = 4
missing = 6 - 4 = 2   ✓

8. Example input and output¶

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 বাদ)

9. Brute force thinking¶

প্রথম সরল চিন্তা: 0 থেকে n পর্যন্ত প্রতিটা সংখ্যার জন্য পুরো array খুঁজে দেখি সেটা আছে কি না; যেটা পাই না, সেটাই missing।

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 ধরা। আর গাণিতিক মোচড়: পুরোটা না খুঁজে শুধু যোগফলের পার্থক্য দেখো।

14. Step-by-step dry run¶

Input nums = [0, 1] (এখানে n = 2, range 0..2):

seen = {0, 1}।
candidate = 0: 0 in seen? হ্যাঁ → এগোও।
candidate = 1: 1 in seen? হ্যাঁ → এগোও।
candidate = 2: 2 in seen? না → return 2।

15. Python solution¶

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 // ঠিক মান দেয়।

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!।

18. Time complexity¶

O(n) — set version array একবার set-এ তোলে আর range একবার scan করে; math version দুটো যোগফলেই O(n)।

19. Space complexity¶

Set version O(n) (পুরো array set-এ)। Math version O(1) — কোনো extra structure নেই, শুধু দুটো যোগফল; এটাই তার বড় সুবিধা।

20. Common mistakes¶

range ভুল করা — range(n) নয়, range(n + 1), কারণ পূর্ণ range 0..n-এ n+1টা সংখ্যা।
math version-এ / ব্যবহার করা — float দেয়; integer-এর জন্য // দরকার।
বড় n-এ integer overflow নিয়ে দুশ্চিন্তা — Python-এ int arbitrary precision, তাই নিরাপদ (তবে C++/Java-তে এটা আসল সমস্যা; সেখানে XOR trick বেশি নিরাপদ)।

21. Which basic problem this inherits from¶

ভিত্তি: seen-set (Pattern 4) দিয়ে absence ধরা; বিকল্পে Gauss-এর যোগফল সূত্র — দেখো ../../01-math-based-programming-fundamentals/ (counting ও sum formula) আর ../patterns.md-র Pattern 4।

22. Similar harder problems¶

Find the Duplicate Number — https://leetcode.com/problems/find-the-duplicate-number/ (উল্টোটা — কে দুবার আছে; cycle detection)
Find All Numbers Disappeared in an Array — https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/ (একাধিক missing)
Single Number — https://leetcode.com/problems/single-number/ (XOR দিয়ে O(1) space)

23. Pattern learned¶

Seen-set + known-range trick: পূর্ণ range জানা থাকলে set দিয়ে absence ধরো, নয়তো যোগফলের পার্থক্যে এক লাফে বের করো।

24. Final summary¶

ভবিষ্যতের আমাকে: "0..n থেকে একটা missing" দেখলে দুটো অস্ত্র — seen-set (general, O(n) space) আর sum formula (O(1) space)। range জানা থাকলে পুরোটা না খুঁজে শুধু পার্থক্য দেখার অভ্যাস করো।

25. JavaScript solution (with test cases)¶

দুই অস্ত্র — seen-set (general) আর Gauss sum formula (O(1) space)।

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)।

26. TypeScript solution (with test cases)¶

function missingNumber(nums: number[]): number {
  const seen: Set<number> = new Set(nums);
  for (let c = 0; c <= nums.length; c++) {
    if (!seen.has(c)) return c;
  }
  return -1;
}
function missingNumberMath(nums: number[]): number {
  const n = nums.length;
  const total = (n * (n + 1)) / 2;
  return total - nums.reduce((a: number, b: number) => a + b, 0);
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(missingNumber([3, 0, 1]), 2, "basic");
expect(missingNumber([1]), 0, "edge-0");
expect(missingNumberMath([9, 6, 4, 2, 3, 5, 7, 0, 1]), 8, "math");
console.log("সব TS test pass!");

TS টীকা: reduce-এর accumulator/element-কে number annotate করায় callback-এ type নিশ্চিত; দুই approach একই signature (number[]) => number রাখায় caller নির্বিঘ্নে যেকোনোটা বেছে নিতে পারে।

27. কোথায় কাজে লাগে (real-world use)¶

Sequence integrity: 0..n ক্রমিক id/packet-এর মধ্যে কোনটা missing তা ধরা (dropped packet detection)।
Attendance/roster: সম্পূর্ণ তালিকা থেকে কোন একটি অনুপস্থিত তা বের করা।
Checksum/sanity: জানা মোট থেকে আসল যোগফল বিয়োগ করে হারানো মান নির্ণয় (O(1) math trick)।
DB sharding: ক্রমিক shard/slot-এর কোনটা allocate হয়নি তা খোঁজা।
Versioning: ক্রমিক revision number-এ gap detect করা।
Resource pool: 0..n slot-এর প্রথম খালি slot বরাদ্দে।

মূল pattern: পূর্ণ range জানা থাকলে set দিয়ে absence ধরো, নয়তো যোগফলের পার্থক্যে এক লাফে — range-knowledge-ই key।

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