Problem link ও উৎস
- **Original source:** LeetCode — Maximum XOR of Two Numbers in an Array
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 4: Bit Manipulation → maximum XOR, greedy by bit / trie
- **Difficulty:** Hard
- **Pattern:** greedy by bit / trie (উপরের bit থেকে greedy, hash set/trie দিয়ে check)
- **Basic idea inherited from:** 060 — Odd One Out using XOR (XOR-এর ধর্ম, এক ধাপ গভীরে)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা non-negative integer array দেওয়া আছে। তোমাকে দুটো সংখ্যা `a` আর `b` বেছে নিতে হবে (একই index দুবার নয়) যাদের `a ^ b` সবচেয়ে **বড়**। সেই সর্বোচ্চ XOR মানটা ফেরত দাও।
যেমন `[3, 10, 5, 25, 2, 8]`:
```text
সবচেয়ে বড় XOR: 5 ^ 25 = 28
```
মানে সব সম্ভাব্য জোড়ার মধ্যে কোনটার XOR সর্বোচ্চ, সেটা খুঁজে বের করা।
### Input ও output {#6-example-input-and-output}
```text
array -> output (max XOR)
-----------------------------------------------
[3, 10, 5, 25, 2, 8] -> 28 (5 ^ 25)
[0] -> 0 (একটাই সংখ্যা, জোড়া নেই)
[2, 4] -> 6 (2 ^ 4 = 110)
[8, 10, 2] -> 10 (8 ^ 2 = 10)
[0, 0] -> 0 (দুটোই 0)
[1, 2, 3, 4, 5, 6, 7] -> 7 (যেমন 1 ^ 6 = 7)
```
edge case: `[0]` (একটাই element) — কোনো জোড়া নেই, তাই উত্তর `0`। `[0, 0]` → `0 ^ 0 = 0`। সব সংখ্যা non-negative ধরা হয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি সবচেয়ে দামি জুটি খুঁজছ — কিন্তু "দাম" নির্ধারিত হয় সবচেয়ে বড় ঘর থেকে। যেন একটা সংখ্যা যত বড় তত দামি, আর বড় সংখ্যা মানে আগে উপরের digit বড় হওয়া।
তুমি লোভী (greedy) হয়ে ভাবো — "সবচেয়ে উপরের ঘরে কি 1 পেতে পারি?" সম্ভব হলে নিয়ে নাও (কারণ উপরের 1 নিচের সব কিছুর চেয়ে দামি)। তারপর পরের ঘরে একই প্রশ্ন, কিন্তু এবার শর্ত: "উপরে যা নিয়েছি সেটা ধরে রেখে এই ঘরেও কি 1 পাওয়া যায়?" এভাবে উপর থেকে নিচে প্রতি ঘরে যতটা পারো 1 নিতে নিতে নামো — শেষে হাতে সবচেয়ে দামি জুটির মান।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দাঁড়িয়ে আছে **060 (Odd One Out)**-এর XOR-ধর্মের উপর — বিশেষ করে `a ^ b = c ⟺ a ^ c = b`, যেটা hash-set check-এর মূল। সাথে লাগে bit পড়া (053, 054) আর mask বানানো (055)।
এটা এই level-এর সবচেয়ে গভীর problem — এর "প্রতি bit-এ branch" চিন্তাটাই **binary trie**-র বীজ। trie-র formal পরিচয় পরের কোনো level-এ আসবে; এখানে শুধু গন্ধটা নাও। concept-notes-এ এর teaser আছে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **bit-এর greedy** — উপরের (most significant) bit সবচেয়ে দামি।
কেন? কারণ উপরের একটা 1, নিচের সব 1 মিলেও তার চেয়ে বড় (`1000 > 0111`)। তাই XOR বড় করতে চাইলে আগে সবচেয়ে উপরের bit-টা 1 করার চেষ্টা করো, তারপর তার নিচেরটা, এভাবে নেমে আসো।
প্রতি bit-এ প্রশ্ন: "এ পর্যন্ত যা পেয়েছি (`ans`), তার সাথে এই bit-টা 1 যোগ করা কি সম্ভব — মানে array-তে এমন দুটো সংখ্যা আছে যাদের উপরের অংশ XOR করলে এই candidate পাওয়া যায়?" সম্ভব হলে সেই bit রেখে দাও।
Check করার চালাকি (hash set): `a ^ b = c` মানে `a ^ c = b`। তাই candidate prefix `c` সম্ভব কিনা দেখতে — প্রতিটা সংখ্যার prefix `p`-র জন্য `p ^ c` ও set-এ আছে কিনা দেখি। থাকলে এমন জোড়া আছে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
greedy না জানলে, সব জোড়া দেখাই সবচেয়ে স্বাভাবিক — প্রতিটা জোড়ার XOR বের করে সর্বোচ্চটা নিই:
```python
def max_xor_brute(nums):
best = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
best = max(best, nums[i] ^ nums[j])
return best
```
কাজ করে — সব `n(n-1)/2` জোড়া দেখে সবচেয়ে বড় XOR। ছোট array-তে একদম ঠিক। কিন্তু array বড় হলে?
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
brute force-এ দুটো nested loop — মোট `O(n²)` জোড়া। `n = 100000` হলে প্রায় `10^10` জোড়া, interview-তে Time Limit Exceeded।
```text
n = 100000:
brute (O(n²)) : ~5 × 10^9 জোড়া (অসম্ভব ধীর)
greedy by bit : O(n × 32) (~3.2M, চটজলদি)
```
মূল অপচয়: সব জোড়া দেখা। অথচ greedy-তে আমরা উত্তরটা **bit by bit গড়ি** — প্রতি bit-এ শুধু "এই bit 1 হতে পারে কিনা" যাচাই করি, সব জোড়া না দেখে। 32টা bit × n — অনেক দ্রুত।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
উপরের bit থেকে greedy — প্রতি ধাপে candidate prefix বানিয়ে hash set দিয়ে check করো:
```python
def max_xor(nums):
ans = 0
for bit in range(31, -1, -1): # উপরের bit থেকে নিচে
ans <<= 1 # উত্তরে নতুন একটা ঘর যোগ
candidate = ans | 1 # এই bit 1 করার চেষ্টা
prefixes = {x >> bit for x in nums} # প্রতিটা সংখ্যার উপরের অংশ
# candidate সম্ভব? a ^ b = candidate <=> a ^ candidate = b (set-এ আছে?)
if any((p ^ candidate) in prefixes for p in prefixes):
ans = candidate # হ্যাঁ! bit 1 রাখলাম
# নাহলে ans-এর শেষ bit 0-ই থাকে
return ans
```
প্রতি bit-এ একটা set বানিয়ে check — মোট `O(n × 32)`। সব জোড়া দেখার দরকার নেই।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **উত্তরটা একসাথে খুঁজো না — উপরের bit থেকে এক এক bit করে গড়ো; প্রতি ধাপে শুধু জিজ্ঞেস করো "এই bit-টা কি 1 হতে পারে?", আর সেটা যাচাই করো `a ^ b = c ⟺ a ^ c = b` দিয়ে hash set-এ।**
brute force পুরো জোড়া তুলনা করে। কিন্তু greedy insight: উপরের bit এত দামি যে সেটা 1 করা গেলে কখনো ছাড়ব না (নিচের সব মিলেও তার চেয়ে ছোট)। তাই উত্তর গড়ি উপর থেকে — প্রতি bit-এ "1 চাই" ধরে নিয়ে দেখি সম্ভব কিনা, সম্ভব হলে রাখি, নাহলে 0 রেখে নিচে নামি। আর "সম্ভব কিনা"-র চালাক check: যদি candidate prefix `c` চাই, তবে কোনো prefix `p`-র জন্য `p ^ c`-ও set-এ থাকতে হবে (কারণ `p ^ c = অন্য prefix` হলেই `p ^ অন্য = c`)। এই **প্রতি-bit-এ branch** চিন্তাটাই binary trie — প্রতিটা সংখ্যা trie-তে ঢোকাও, query-র সময় প্রতি ধাপে **উল্টো** bit-এর দিকে যেতে চেষ্টা করো (উল্টো = XOR-এ 1)।
### ছবিতে বোঝা {#5-visual-explanation}
কেন উপরের bit দামি:
```text
1 0 0 0 = 8
0 1 1 1 = 7
উপরের একটা 1 (8) > নিচের তিনটা 1 (7)
তাই XOR বড় করতে আগে উপরের bit লক্ষ্য
```
greedy চলা (`[5, 25]`, এদের XOR দেখি, 5-bit-এ):
```text
5 = 0 0 1 0 1
25 = 1 1 0 0 1
XOR= 1 1 1 0 0 = 28
bit 4 (16): 5-এ 0, 25-এ 1 -> আলাদা -> XOR-এ 1 ✓ (দামি bit পেলাম)
bit 3 (8) : 5-এ 0, 25-এ 1 -> আলাদা -> 1 ✓
bit 2 (4) : 5-এ 1, 25-এ 0 -> আলাদা -> 1 ✓
bit 1 (2) : 5-এ 0, 25-এ 0 -> একই -> 0
bit 0 (1) : 5-এ 1, 25-এ 1 -> একই -> 0
উত্তর: 11100 = 28
```
greedy উপর থেকে এক এক bit নিয়ে এই 28-এ পৌঁছায় — সব জোড়া না দেখেই।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [2, 4]` (3-bit যথেষ্ট, কিন্তু ধারণার জন্য উপরের bit থেকে):
```text
2 = 010, 4 = 100
লক্ষ্য: 2 ^ 4 = 110 = 6
```
bit 2 (মান 4) থেকে:
| bit | ans আগে | candidate (ans<<1 \| 1) | prefixes = {x >> bit} | candidate সম্ভব? | ans পরে |
| --- | --- | --- | --- | --- | --- |
| 2 | 0 | 1 | {2>>2, 4>>2} = {0, 1} | 0^1=1 ∈ set? হ্যাঁ | 1 |
| 1 | 1 | 11 (=3) | {2>>1, 4>>1} = {1, 2} | কোনো p-তে p^3 ∈ set? 1^3=2 ∈ {1,2} হ্যাঁ | 3 |
| 0 | 3 | 111 (=7) | {2, 4} | p^7 ∈ {2,4}? 2^7=5 না, 4^7=3 না | 6 (শেষ bit 0) |
শেষে `ans = 6` → `2 ^ 4 = 6` ✓। উপর থেকে bit গড়ে 110-এ পৌঁছাল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def max_xor(nums):
"""array থেকে দুটো সংখ্যার সর্বোচ্চ XOR, greedy by bit + hash set।"""
ans = 0
for bit in range(31, -1, -1): # উপরের bit থেকে নিচে
ans <<= 1 # উত্তরে নতুন ঘর যোগ
candidate = ans | 1 # এই bit 1 করার চেষ্টা
prefixes = {x >> bit for x in nums} # প্রতিটা সংখ্যার উপরের অংশ
# a ^ b = candidate <=> a ^ candidate = b ; set-এ এমন জোড়া আছে?
if any((p ^ candidate) in prefixes for p in prefixes):
ans = candidate # সম্ভব -> bit 1 রাখো
return ans
def max_xor_brute(nums):
"""একই উত্তর সব জোড়া দেখে (যাচাইয়ের জন্য)।"""
best = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
best = max(best, nums[i] ^ nums[j])
return best
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert max_xor([3, 10, 5, 25, 2, 8]) == 28 # 5 ^ 25
assert max_xor([0]) == 0 # একটাই সংখ্যা
assert max_xor([2, 4]) == 6 # 2 ^ 4 = 110
assert max_xor([8, 10, 2]) == 10 # 8 ^ 2
assert max_xor([0, 0]) == 0
assert max_xor([1, 2, 3, 4, 5, 6, 7]) == 7
# greedy আর brute force একই উত্তর দেয় (random array-তে)
import random
for _ in range(200):
n = random.randint(1, 12)
nums = [random.randint(0, 1000) for _ in range(n)]
assert max_xor(nums) == max_xor_brute(nums)
print(max_xor([3, 10, 5, 25, 2, 8])) # 28
print(max_xor([2, 4])) # 6
print(max_xor([8, 10, 2])) # 10
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
for bit in range(31, -1, -1):
ans <<= 1
candidate = ans | 1
```
উপরের bit (31) থেকে নিচের bit (0) পর্যন্ত যাই। প্রতি ধাপে `ans`-কে এক ঘর বাঁয়ে সরাই (নতুন একটা bit-এর জায়গা করি), আর `candidate = ans | 1` দিয়ে সেই নতুন bit 1 করার চেষ্টা করি।
```text
prefixes = {x >> bit for x in nums}
if any((p ^ candidate) in prefixes for p in prefixes):
ans = candidate
```
প্রতিটা সংখ্যার উপরের অংশ (`x >> bit`) একটা set-এ রাখি। candidate prefix সম্ভব কিনা দেখি `a ^ b = candidate ⟺ a ^ candidate = b` দিয়ে — কোনো prefix `p`-র জন্য `p ^ candidate`-ও set-এ থাকলে এমন জোড়া আছে, তাই bit 1 রাখি। নাহলে `ans`-এর শেষ bit 0-ই থাকে (কারণ `ans <<= 1`-এ শূন্য এসেছিল)।
```text
best = max(best, nums[i] ^ nums[j])
```
brute version: সব জোড়ার XOR-এর সর্বোচ্চ — যাচাইয়ের জন্য।
`assert` আর random `for` loop greedy-কে brute force-এর সাথে 200টা random array-তে মিলিয়ে নিচ্ছে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
28
6
10
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: `[3,10,5,25,2,8]`→28 (5^25), `[2,4]`→6, `[8,10,2]`→10 (8^2)। সব `assert` (random cross-check loop সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n × B)** — B = bit-সংখ্যা (এখানে 32)। প্রতিটা bit-এর জন্য একটা set বানাই (O(n)) আর check করি (O(n))। মোট `O(n × 32) = O(n)` কার্যত। brute force-এর `O(n²)`-এর তুলনায় বিশাল উন্নতি। (trie দিয়েও একই `O(n × B)`।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — প্রতি bit-এ একটা `prefixes` set, বড়জোর n টা element। trie version-এও O(n × B) node, কিন্তু কার্যত O(n)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **নিচের bit থেকে শুরু করা** — greedy অবশ্যই **উপরের** (most significant) bit থেকে; উপরের 1 নিচের সবকিছুর চেয়ে দামি।
2. **check-এর identity ভুল করা** — `a ^ b = c ⟺ a ^ c = b`; এটাই hash-set check-এর ভিত্তি, ভুলে গেলে পুরো logic ভাঙে।
3. **একই index দুবার ভাবা** — জোড়ায় দুটো ভিন্ন element; তবে এই hash-set পদ্ধতিতে দুটো ভিন্ন prefix লাগে বলে স্বাভাবিকভাবেই ঠিক থাকে (একই সংখ্যার XOR নিজে = 0, max-এ গুরুত্বহীন)।
4. **bit-সংখ্যা কম নেওয়া** — মানের সীমা অনুযায়ী যথেষ্ট bit (যেমন 32) ধরতে হবে, নাহলে উপরের bit মিস হবে।
5. **brute force দিয়ে বড় n করা** — `O(n²)` বড় array-তে TLE; greedy/trie লাগে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Maximum XOR of Two Numbers in an Array** (