060 — Odd One Out using XOR¶
এবার XOR-এর আসল জাদু। একটা array-তে প্রতিটা সংখ্যা ঠিক দুবার করে আছে — শুধু একটা ছাড়া, যেটা একবার। সেই একলা সংখ্যাটা খুঁজে বের করো। Hash map বা sorting দিয়ে করা যায়, কিন্তু XOR দিয়ে এক loop-এ, O(1) space-এ — এত সুন্দর সমাধান যে দেখলে মুগ্ধ হবে। interview-তে "Single Number" নামে classic। চলো বুঝি।
Source¶
- Original source: LeetCode — Single Number
- Platform: LeetCode — https://leetcode.com/problems/single-number/
- 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-এর ধর্ম)
1. Problem in simple words¶
একটা integer array দেওয়া আছে যেখানে প্রতিটা সংখ্যা ঠিক দুবার করে আছে — শুধু একটা সংখ্যা একবার। সেই একলা (unique) সংখ্যাটা খুঁজে বের করো।
যেমন [4, 1, 2, 1, 2]:
- 1 আছে দুবার, 2 আছে দুবার
- 4 আছে একবার → উত্তর
4
নিশ্চয়তা: ঠিক একটা সংখ্যাই একলা, বাকি সবাই জোড়ায়।
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 সংখ্যা।
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-এর এই ভিত্তি কাজে লাগে।
4. Real-life analogy¶
ভাবো একটা পার্টিতে সবাই জোড়ায় জোড়ায় এসেছে — প্রতিটা মানুষের সাথে তার সঙ্গী। শুধু একজন একা এসেছে।
এখন একটা খেলা: দুজন একই রকম মানুষ মুখোমুখি দাঁড়ালে দুজনেই "ভ্যানিশ" হয়ে যায় (a ^ a = 0)। সবাই যেহেতু জোড়ায় আছে, তারা একে একে মুখোমুখি দাঁড়িয়ে ভ্যানিশ হয়ে যাবে। শেষে ঘরে যে দাঁড়িয়ে থাকবে — সে-ই একলা মানুষ। কাকে কখন মুখোমুখি দাঁড় করালে তাতে কিছু যায় আসে না (order matters না) — ফল একই।
5. Visual explanation¶
XOR টেবিল — আলাদা হলে 1, একই হলে 0:
পুরো array XOR ([4, 1, 2, 1, 2]), বাঁ থেকে জমা করি:
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 টিকে রইল) ✓
পুনর্বিন্যাস করে দেখো কেন কাটে:
6. Example input and output¶
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-এ কেটে যায় — কোনো সমস্যা নেই।
7. Brute force thinking¶
XOR না জানলে, hash map দিয়ে গোনা সবচেয়ে স্বাভাবিক — প্রতিটা সংখ্যার count রাখো, শেষে যার count 1 সেটাই উত্তর:
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।
interview-তে যখন বলে "constant space-এ করো", তখন hash map বাদ — XOR-ই একমাত্র পরিষ্কার পথ। এটাই এই problem-এর মূল আকর্ষণ।
9. Better thinking¶
পুরো array একটা accumulator-এ XOR করো — জোড়াগুলো নিজে নিজে কাটবে:
একটাই 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-এ দুটো একলা সংখ্যার ক্ষেত্রেও কাজে লাগবে — শুধু একটু চালাকি যোগ করতে হবে।
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-ই থাকে।
12. Python solution¶
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¶
এটাই হৃদয়। acc শুরু হয় 0 (a ^ 0 = a, তাই নিরাপদ শুরু)। প্রতিটা সংখ্যাকে acc-এর সাথে XOR করি। যেহেতু x ^ x = 0 আর order matters না, প্রতিটা জোড়া একে অপরকে বাতিল করে; শেষে শুধু একলা সংখ্যাটা acc-এ থাকে।
hash-map version: প্রতিটা সংখ্যার count বাড়াই, পরে যার count 1 সে উত্তর — যাচাইয়ের জন্য।
assert লাইন আর random for loop দুই method-কে 200টা random ক্ষেত্রে (সব জোড়া + একটা সত্যিকারের একলা) মিলিয়ে নিচ্ছে। সব ঠিক থাকলে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম তিন লাইন তিনটা print থেকে: [4,1,2,1,2]→4, [2,2,1]→1, [1]→1। সব assert (random cross-check loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।
15. Time complexity¶
O(n) — array-র প্রতিটা element একবার করে XOR করছি, ব্যস। sorting বা nested loop নেই।
16. Space complexity¶
O(1) — শুধু একটা accumulator acc। hash-map version-এ O(n) লাগত, কিন্তু XOR-এ একটাই int যথেষ্ট — এটাই এর সবচেয়ে বড় জয়।
17. Common mistakes¶
^কে power ভাবা — Python-এ XOR হলো^, power হলো**।4 ^ 1 = 5(XOR)।- acc-এর ভুল শুরু —
acc = 0দিয়ে শুরু করতে হবে (a ^ 0 = a)। অন্য কিছু দিয়ে শুরু করলে উত্তর নষ্ট। - XOR দিয়ে সব duplicate problem solve করতে চাওয়া — XOR cancel শুধু জোড়ার ক্ষেত্রে কাজ করে। তিনবার করে এলে (একটা একবার) অন্য কৌশল লাগে (bit count mod 3)। (README #7।)
- জোড়া নিশ্চয়তা ভুলে যাওয়া — problem-এর শর্ত: একটা ছাড়া বাকি সব ঠিক দুবার। শর্ত না মানলে XOR ভুল উত্তর দেবে।
- 0-কে ভয় পাওয়া —
0array-তে জোড়ায় থাকলেও XOR-এ ঠিকঠাক কাটে; আলাদা সামলানোর দরকার নেই।
18. Harder problems that inherit this idea¶
- 061 — Find Two Unique Numbers (এই repo) — দুটো সংখ্যা একলা; XOR + partition।
- 066 — Maximum XOR Pair (এই repo) — XOR-এর greedy/trie প্রয়োগ।
- LeetCode — Single Number II (https://leetcode.com/problems/single-number-ii/) — প্রতিটা তিনবার, একটা একবার; bit count mod 3।
- LeetCode — Missing Number (https://leetcode.com/problems/missing-number/) — index আর value XOR করে missing খোঁজা।
19. Pattern learned¶
XOR cancellation — a ^ a = 0 আর a ^ 0 = a দিয়ে জোড়া বাতিল করে একলা খুঁজে বের করা, O(1) space-এ। বড় শিক্ষা: জোড়ায় আসা জিনিস XOR-এ নিজে নিজে কাটে — গোনা বা hash map ছাড়াই একলা টিকে থাকে। কিন্তু এটা শুধু জোড়ার ক্ষেত্রে।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "একলা সংখ্যা = পুরো array XOR (acc ^= x)। জোড়া নিজে নিজে কাটে (a ^ a = 0), একলা টেকে; O(1) space। 'constant space' বা 'প্রতিটা দুবার' শুনলেই XOR মনে করব।"
পরের ধাপ → 061 — Find Two Unique Numbers (এবার দুটো সংখ্যা একলা — XOR-এর সাথে একটু চালাকি লাগবে)। সম্পর্কিত → 066 — Maximum XOR Pair · 057 — Toggle ith Bit।
ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।
21. JavaScript solution (with test cases)¶
JS-এ XOR হলো ^ (power নয়!), আর accumulator 0 থেকে শুরু — Python-এর হুবহু।
// 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 লাগত।
22. TypeScript solution (with test cases)¶
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<readonly [number[], number]> = [
[[4, 1, 2, 1, 2], 4], [[2, 2, 1], 1], [[1], 1], [[7, 3, 7], 3],
[[0, 1, 0], 1], [[5, 5, 9, 9, 13], 13], [[-3, -3, 8], 8],
];
for (const [arr, want] of cases) expect(oddOneOut(arr), want, `[${arr}]`);
console.log("সব TS test pass!");
TS টীকা: parameter
number[]declare করায় ভুলেstring[]বা mixed array পাঠানো compile-time-এ আটকায় —^শুধু number-এ অর্থপূর্ণ, type সেটা নিশ্চিত করে।
23. কোথায় কাজে লাগে (real-world use)¶
- Checksum / parity / error detection: XOR দিয়ে data block-এর parity বানানো ও যাচাই (RAID, ECC memory, transmission)।
- Toggle state: কোনো flag বারবার flip (
x ^= mask) — UI toggle, feature switch, simple cipher। - In-place swap (no temp):
a ^= b; b ^= a; a ^= b;— মাঝে variable ছাড়া দুই value অদলবদল। - Find the missing/duplicate: index আর value XOR করে এক pass O(1) space-এ missing number খোঁজা।
মূল pattern — "জোড়া হওয়া জিনিস XOR-এ নিজে নিজে কাটে (
a ^ a = 0), একলা টেকে — O(1) space" — cancellation, parity, RAID reconstruction জুড়ে বড় ছবিতে ফেরে।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি নেই — বরং "common interview pattern" / "Google-style pattern"।