066 — Maximum XOR Pair

Level 4-এর শেষ problem — আর এটা trie-র দরজায় টোকা দেয়। একটা array থেকে দুটো সংখ্যা বেছে নাও যাদের XOR সবচেয়ে বড়। naive ভাবে সব জোড়া দেখলে O(n²); কিন্তু একটা greedy চিন্তা আছে — "সবচেয়ে উপরের bit থেকে নেমে এসে প্রতি ধাপে জিজ্ঞেস করো, এই bit-টা কি উত্তরে 1 হতে পারে?" এই branch-by-bit চিন্তাটাই binary trie। Hard, interview-তে "Maximum XOR of Two Numbers in an Array"। চলো শেষটা করি।

Source

• Original source: LeetCode — Maximum XOR of Two Numbers in an Array
• Platform: LeetCode — https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
• 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-এর ধর্ম, এক ধাপ গভীরে)

1. Problem in simple words

একটা non-negative integer array দেওয়া আছে। তোমাকে দুটো সংখ্যা a আর b বেছে নিতে হবে (একই index দুবার নয়) যাদের a ^ b সবচেয়ে বড়। সেই সর্বোচ্চ XOR মানটা ফেরত দাও।

যেমন [3, 10, 5, 25, 2, 8]:

সবচেয়ে বড় XOR: 5 ^ 25 = 28

মানে সব সম্ভাব্য জোড়ার মধ্যে কোনটার XOR সর্বোচ্চ, সেটা খুঁজে বের করা।

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-এ আছে কিনা দেখি। থাকলে এমন জোড়া আছে।

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 আছে।

4. Real-life analogy

ভাবো তুমি সবচেয়ে দামি জুটি খুঁজছ — কিন্তু "দাম" নির্ধারিত হয় সবচেয়ে বড় ঘর থেকে। যেন একটা সংখ্যা যত বড় তত দামি, আর বড় সংখ্যা মানে আগে উপরের digit বড় হওয়া।

তুমি লোভী (greedy) হয়ে ভাবো — "সবচেয়ে উপরের ঘরে কি 1 পেতে পারি?" সম্ভব হলে নিয়ে নাও (কারণ উপরের 1 নিচের সব কিছুর চেয়ে দামি)। তারপর পরের ঘরে একই প্রশ্ন, কিন্তু এবার শর্ত: "উপরে যা নিয়েছি সেটা ধরে রেখে এই ঘরেও কি 1 পাওয়া যায়?" এভাবে উপর থেকে নিচে প্রতি ঘরে যতটা পারো 1 নিতে নিতে নামো — শেষে হাতে সবচেয়ে দামি জুটির মান।

5. Visual explanation

কেন উপরের bit দামি:

1 0 0 0  = 8
0 1 1 1  = 7
উপরের একটা 1 (8) > নিচের তিনটা 1 (7)
তাই XOR বড় করতে আগে উপরের bit লক্ষ্য

greedy চলা ([5, 25], এদের XOR দেখি, 5-bit-এ):

 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-এ পৌঁছায় — সব জোড়া না দেখেই।

6. Example input and output

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 ধরা হয়।

7. Brute force thinking

greedy না জানলে, সব জোড়া দেখাই সবচেয়ে স্বাভাবিক — প্রতিটা জোড়ার XOR বের করে সর্বোচ্চটা নিই:

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।

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 করো:

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

11. Step-by-step dry run

nums = [2, 4] (3-bit যথেষ্ট, কিন্তু ধারণার জন্য উপরের bit থেকে):

2 = 010, 4 = 100
লক্ষ্য: 2 ^ 4 = 110 = 6

bit 2 (মান 4) থেকে:

bit	ans আগে	candidate (ans<<1 | 1)	prefixes =	candidate সম্ভব?	ans পরে
2	0	1	{2>>2, 4>>2} =	0^1=1 ∈ set? হ্যাঁ	1
1	1	11 (=3)	{2>>1, 4>>1} =	কোনো 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-এ পৌঁছাল।

12. Python solution

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

for bit in range(31, -1, -1):
    ans <<= 1
    candidate = ans | 1

উপরের bit (31) থেকে নিচের bit (0) পর্যন্ত যাই। প্রতি ধাপে ans-কে এক ঘর বাঁয়ে সরাই (নতুন একটা bit-এর জায়গা করি), আর candidate = ans | 1 দিয়ে সেই নতুন bit 1 করার চেষ্টা করি।

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-এ শূন্য এসেছিল)।

best = max(best, nums[i] ^ nums[j])

brute version: সব জোড়ার XOR-এর সর্বোচ্চ — যাচাইয়ের জন্য।

assert আর random for loop greedy-কে brute force-এর সাথে 200টা random array-তে মিলিয়ে নিচ্ছে। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

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

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 লাগে।

18. Harder problems that inherit this idea

• LeetCode — Maximum XOR of Two Numbers in an Array (https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) — এই problem-এরই মূল রূপ।
• LeetCode — Maximum XOR With an Element From Array (https://leetcode.com/problems/maximum-xor-with-an-element-from-array/) — constraint সহ max XOR, trie জরুরি।
• LeetCode — Count Pairs With XOR in a Range (https://leetcode.com/problems/count-pairs-with-xor-in-a-range/) — XOR trie-র গভীর প্রয়োগ।
• CSES / Codeforces — XOR trie problems (https://cses.fi/problemset/) — binary trie-র সংগ্রহ।

19. Pattern learned

Maximum XOR via greedy-by-bit (trie) — উপরের bit থেকে এক এক bit করে উত্তর গড়া, প্রতি ধাপে a ^ c = b identity দিয়ে hash set/trie-তে "এই bit 1 সম্ভব?" যাচাই। বড় শিক্ষা: উপরের bit সবচেয়ে দামি, তাই উত্তর গড়ো উপর থেকে নিচে; সব জোড়া না দেখে প্রতি bit-এ branch করলেই O(n²) থেকে O(n × B)। এই branch-by-bit-ই binary trie।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "max XOR pair = উপরের bit থেকে greedy; প্রতি bit-এ 'এটা 1 হতে পারে?' a ^ c = b দিয়ে hash set-এ যাচাই। সব জোড়া (O(n²)) দেখার বদলে branch-by-bit (O(n×32)) — এটাই binary trie-র গন্ধ।"

এটাই Level 4-এর শেষ problem! পরের ধাপ → Level 5: Prefix, Difference, Contribution (bit ছেড়ে আবার যোগফলের জগতে — "আগে থেকে হিসেব করে রাখা"-র জাদু)। সম্পর্কিত → 060 — Odd One Out using XOR · 061 — Find Two Unique Numbers।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

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