Problem link ও উৎস
- **Original source:** LeetCode — Single Number
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 4: Bit Manipulation → XOR self-inverse
- **Difficulty:** Easy
- **Pattern:** XOR cancel (`a ^ a = 0` দিয়ে জোড়া বাতিল)
- **Basic idea inherited from:** 053 — Binary Representation (bit বোঝা; এখানে XOR-এর ধর্ম)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array দেওয়া আছে যেখানে প্রতিটা সংখ্যা ঠিক **দুবার** করে আছে — শুধু একটা সংখ্যা **একবার**। সেই একলা (unique) সংখ্যাটা খুঁজে বের করো।
যেমন `[4, 1, 2, 1, 2]`:
- 1 আছে দুবার, 2 আছে দুবার
- 4 আছে একবার → উত্তর `4`
নিশ্চয়তা: ঠিক একটা সংখ্যাই একলা, বাকি সবাই জোড়ায়।
### Input ও output {#6-example-input-and-output}
```text
array -> output
-------------------------------
[4, 1, 2, 1, 2] -> 4
[2, 2, 1] -> 1
[1] -> 1 (একটাই element)
[7, 3, 7] -> 3
[0, 1, 0] -> 1 (0-ও জোড়ায় কাটে)
[5, 5, 9, 9, 13] -> 13
[-3, -3, 8] -> 8 (negative-ও কাজ করে)
```
edge case: `[1]` (একটাই element) → সেটাই উত্তর। আর `0` জোড়ায় থাকলেও XOR-এ কেটে যায় — কোনো সমস্যা নেই।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পার্টিতে সবাই জোড়ায় জোড়ায় এসেছে — প্রতিটা মানুষের সাথে তার সঙ্গী। শুধু একজন একা এসেছে।
এখন একটা খেলা: দুজন একই রকম মানুষ মুখোমুখি দাঁড়ালে দুজনেই "ভ্যানিশ" হয়ে যায় (`a ^ a = 0`)। সবাই যেহেতু জোড়ায় আছে, তারা একে একে মুখোমুখি দাঁড়িয়ে ভ্যানিশ হয়ে যাবে। শেষে ঘরে যে দাঁড়িয়ে থাকবে — সে-ই একলা মানুষ। কাকে কখন মুখোমুখি দাঁড় করালে তাতে কিছু যায় আসে না (order matters না) — ফল একই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দাঁড়িয়ে আছে **053 (Binary Representation)** আর 057-এ পরিচয় হওয়া XOR operator-এর উপর। XOR আসলে bit-by-bit কাজ করে — প্রতিটা bit-position-এ আলাদাভাবে "জোড় সংখ্যক 1 হলে 0, বিজোড় হলে 1"। সেই bit-চিন্তা না থাকলে কেন জোড়া কাটে সেটা বোঝা কঠিন।
আর এই 060 হলো **061 (Find Two Unique Numbers)**-এর সরাসরি ভিত্তি — সেখানে দুটো সংখ্যা একলা, তখন এই XOR-cancel idea-কে আরও এক ধাপ এগিয়ে নিতে হয়। আর **066 (Maximum XOR Pair)**-এও XOR-এর এই ভিত্তি কাজে লাগে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **XOR-এর self-inverse ধর্ম**। XOR (`^`)-এর তিনটা চমৎকার নিয়ম:
- `a ^ a = 0` — একই জিনিস দুবার XOR করলে কেটে যায়
- `a ^ 0 = a` — 0-এর সাথে XOR করলে অপরিবর্তিত
- order matters না (commutative + associative)
তাই পুরো array-কে একসাথে XOR করলে, **জোড়াগুলো নিজে নিজে বাতিল** হয়ে যায় (প্রতিটা জোড়া `x ^ x = 0`), আর যে একলা সে 0-এর সাথে XOR হয়ে টিকে থাকে। ফলাফল = সেই unique সংখ্যা।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
XOR না জানলে, hash map দিয়ে গোনা সবচেয়ে স্বাভাবিক — প্রতিটা সংখ্যার count রাখো, শেষে যার count 1 সেটাই উত্তর:
```python
def odd_one_out_brute(nums):
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
for x, c in count.items():
if c == 1:
return x
```
কাজ করে — গুনে রাখি, যার count 1 সে একলা। কিন্তু এতে একটা পুরো dictionary লাগে (O(n) extra space)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
brute force time-এ ঠিক আছে (O(n)), কিন্তু **space-এ O(n)** — পুরো hash map রাখতে হয়। XOR সমাধানে কোনো extra structure লাগে না, শুধু একটা accumulator।
```text
hash map : O(n) time, O(n) space (পুরো count টেবিল)
XOR : O(n) time, O(1) space (একটা int যথেষ্ট)
```
interview-তে যখন বলে "constant space-এ করো", তখন hash map বাদ — XOR-ই একমাত্র পরিষ্কার পথ। এটাই এই problem-এর মূল আকর্ষণ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
পুরো array একটা accumulator-এ XOR করো — জোড়াগুলো নিজে নিজে কাটবে:
```python
def odd_one_out(nums):
acc = 0
for x in nums:
acc ^= x
return acc
```
একটাই variable, একটাই pass। O(n) time, O(1) space। জোড়া সংখ্যাগুলো `x ^ x = 0` হয়ে উবে যায়, একলা সংখ্যা `^ 0` হয়ে টিকে থাকে।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **XOR নিজের ছায়া নিজে মুছে দেয় (`a ^ a = 0`); তাই জোড়াগুলোকে আলাদা করে খুঁজতেই হয় না — সব একসাথে XOR করলে তারা নিজেরাই বাতিল হয়ে যায়, একলা টিকে থাকে।**
গোনা বা sorting-এ আমরা "কে কতবার আছে" track করি। কিন্তু XOR-এ track করার দরকারই নেই — জোড়া হওয়া মানেই স্বয়ংক্রিয় বাতিল। আর order matters না বলে আমরা নিশ্চিন্তে এক pass-এ সব XOR করে দিই। এই "জোড়া = নিজে নিজে কাটা" ধর্মই 061-এ দুটো একলা সংখ্যার ক্ষেত্রেও কাজে লাগবে — শুধু একটু চালাকি যোগ করতে হবে।
### ছবিতে বোঝা {#5-visual-explanation}
XOR টেবিল — আলাদা হলে 1, একই হলে 0:
```text
0 ^ 0 = 0 1 ^ 1 = 0 <- একই -> কাটে
0 ^ 1 = 1 1 ^ 0 = 1 <- আলাদা -> টেকে
```
পুরো array XOR (`[4, 1, 2, 1, 2]`), বাঁ থেকে জমা করি:
```text
acc শুরু = 0
0 ^ 4 = 4 (0100)
4 ^ 1 = 5 (0101)
5 ^ 2 = 7 (0111)
7 ^ 1 = 6 (0110)
6 ^ 2 = 4 (0100)
----
উত্তর = 4 (1 আর 2 জোড়ায় কেটে গেল, 4 টিকে রইল) ✓
```
পুনর্বিন্যাস করে দেখো কেন কাটে:
```text
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [4, 1, 2, 1, 2]`:
| step | x | acc আগে | acc ^= x | binary |
| --- | --- | --- | --- | --- |
| 1 | 4 | 0 | 4 | 0100 |
| 2 | 1 | 4 | 5 | 0101 |
| 3 | 2 | 5 | 7 | 0111 |
| 4 | 1 | 7 | 6 | 0110 |
| 5 | 2 | 6 | 4 | 0100 |
শেষে `acc = 4` → উত্তর `4`। লক্ষ করো — মাঝপথে acc নানা মান নেয়, কিন্তু জোড়াগুলো শেষ হতে হতে সব কেটে গিয়ে একলা 4-ই থাকে।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def odd_one_out(nums):
"""প্রতিটা সংখ্যা দুবার, একটা একবার — সেই একলা সংখ্যা XOR দিয়ে খোঁজে।"""
acc = 0
for x in nums:
acc ^= x
return acc
def odd_one_out_count(nums):
"""একই উত্তর hash map দিয়ে (যাচাইয়ের জন্য)।"""
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
for x, c in count.items():
if c == 1:
return x
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert odd_one_out([4, 1, 2, 1, 2]) == 4
assert odd_one_out([2, 2, 1]) == 1
assert odd_one_out([1]) == 1 # একটাই element
assert odd_one_out([7, 3, 7]) == 3
assert odd_one_out([0, 1, 0]) == 1 # 0-ও জোড়ায় কাটে
assert odd_one_out([5, 5, 9, 9, 13]) == 13
assert odd_one_out([-3, -3, 8]) == 8 # negative-ও কাজ করে
# random ভাবে: সব জোড়া + একটা একলা, XOR == hash map
import random
for _ in range(200):
pairs = [random.randint(0, 50) for _ in range(random.randint(0, 6))]
arr = pairs + pairs # প্রতিটা দুবার
unique = random.randint(100, 200) # পরিসর আলাদা, তাই সত্যিই একলা
arr.append(unique)
random.shuffle(arr)
assert odd_one_out(arr) == unique
assert odd_one_out_count(arr) == unique
print(odd_one_out([4, 1, 2, 1, 2])) # 4
print(odd_one_out([2, 2, 1])) # 1
print(odd_one_out([1])) # 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
acc = 0
for x in nums:
acc ^= x
return acc
```
এটাই হৃদয়। `acc` শুরু হয় 0 (`a ^ 0 = a`, তাই নিরাপদ শুরু)। প্রতিটা সংখ্যাকে `acc`-এর সাথে XOR করি। যেহেতু `x ^ x = 0` আর order matters না, প্রতিটা জোড়া একে অপরকে বাতিল করে; শেষে শুধু একলা সংখ্যাটা `acc`-এ থাকে।
```text
count[x] = count.get(x, 0) + 1
```
hash-map version: প্রতিটা সংখ্যার count বাড়াই, পরে যার count 1 সে উত্তর — যাচাইয়ের জন্য।
`assert` লাইন আর random `for` loop দুই method-কে 200টা random ক্ষেত্রে (সব জোড়া + একটা সত্যিকারের একলা) মিলিয়ে নিচ্ছে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
4
1
1
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: `[4,1,2,1,2]`→4, `[2,2,1]`→1, `[1]`→1। সব `assert` (random cross-check loop সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
### JavaScript ও test cases {#21-javascript-solution-with-test-cases}
JS-এ XOR হলো `^` (power নয়!), আর accumulator 0 থেকে শুরু — Python-এর হুবহু।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function oddOneOut(nums) {
let acc = 0;
for (const x of nums) acc ^= x; // জোড়া নিজে নিজে কাটে, একলা টেকে
return acc;
}
// hash map দিয়ে cross-check
function oddOneOutCount(nums) {
const count = new Map();
for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
for (const [x, c] of count) if (c === 1) return x;
return undefined;
}
// ---- test cases (file-এর example + edge case) ----
assert(oddOneOut([4, 1, 2, 1, 2]) === 4, "4");
assert(oddOneOut([2, 2, 1]) === 1, "1");
assert(oddOneOut([1]) === 1, "একটাই element");
assert(oddOneOut([7, 3, 7]) === 3, "3");
assert(oddOneOut([0, 1, 0]) === 1, "0 জোড়ায় কাটে");
assert(oddOneOut([5, 5, 9, 9, 13]) === 13, "13");
assert(oddOneOut([-3, -3, 8]) === 8, "negative");
// random: সব জোড়া + একটা একলা, XOR == hash map
for (let t = 0; t < 200; t++) {
const pairs = [];
const cnt = Math.floor(Math.random() * 6);
for (let i = 0; i < cnt; i++) pairs.push(Math.floor(Math.random() * 50));
const unique = 100 + Math.floor(Math.random() * 100); // পরিসর আলাদা
const arr = [...pairs, ...pairs, unique];
for (let i = arr.length - 1; i > 0; i--) { // shuffle
const j = Math.floor(Math.random() * (i + 1));
[arr[i], arr[j]] = [arr[j], arr[i]];
}
assert(oddOneOut(arr) === unique, "xor random");
assert(oddOneOutCount(arr) === unique, "map random");
}
console.log("সব JS test pass!");
```
> **JS টীকা:** Python-এর মতো এখানেও XOR `^`, power `**` (`4 ^ 1 === 5`, `4 ** 1 === 4`) — গুলিও না। `^` 32-bit signed-এ চলে, কিন্তু example-এর ছোট মানে কোনো সমস্যা নেই; খুব বড় বা negative-bit-heavy সংখ্যায় BigInt লাগত।
### TypeScript ও test cases {#22-typescript-solution-with-test-cases}
```typescript
function oddOneOut(nums: number[]): number {
let acc = 0;
for (const x of nums) acc ^= x;
return acc;
}
function expect(actual: number, expected: number, msg = ""): void {
if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}
const cases: ReadonlyArray