061 — Find Two Unique Numbers¶

060-এ একলা একজনকে XOR দিয়ে খুঁজলে। আজ চ্যালেঞ্জ বাড়ল — এবার দুটো সংখ্যা একলা, বাকি সবাই জোড়ায়। পুরো array XOR করলে পাবে a ^ b — কিন্তু এক গাদা থেকে দুটো আলাদা করবে কীভাবে? এখানেই আসছে এই level-এর সবচেয়ে চালাক trick: একটা set bit ধরে পুরো array-কে দুই দলে ভাগ করা। Medium, interview-তে "Single Number III"। চলো।

Problem link ও উৎস

Original source: LeetCode — Single Number III
Platform: LeetCode — https://leetcode.com/problems/single-number-iii/
Topic: Math-based programming fundamentals → Level 4: Bit Manipulation → XOR partition
Difficulty: Medium
Pattern: XOR partition (XOR all, তারপর একটা set bit দিয়ে দুই দলে ভাগ)
Basic idea inherited from: 060 — Odd One Out using XOR (XOR cancel, এক ধাপ এগিয়ে)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

একটা integer array দেওয়া আছে যেখানে ঠিক দুটো সংখ্যা একবার করে আছে, বাকি প্রতিটা সংখ্যা ঠিক দুবার করে। সেই দুটো একলা (unique) সংখ্যা খুঁজে বের করো।

যেমন [1, 2, 1, 3, 2, 5]:

1 দুবার, 2 দুবার
3 আর 5 একবার করে → উত্তর [3, 5] (যেকোনো ক্রমে)

Input ও output¶

উদাহরণ

array                   ->  output (যেকোনো ক্রম)
-----------------------------------------------
[1, 2, 1, 3, 2, 5]      ->  [3, 5]
[0, 1]                  ->  [0, 1]      (দুটোই একলা, কোনো জোড়া নেই)
[4, 7]                  ->  [4, 7]
[1, 1, 2, 3]            ->  [2, 3]
[8, 8, 9, 0]            ->  [9, 0]
[-1, -1, 5, 6]          ->  [5, 6]      (negative জোড়াও কাটে)

edge case: [0, 1] — কোনো জোড়াই নেই, সরাসরি দুটোই unique; XOR-partition তবু ঠিক কাজ করে। (output-এর ক্রম গুরুত্বপূর্ণ নয়, তাই test-এ sorted মিলিয়ে নেব।)

চেনা উদাহরণে বোঝা¶

ভাবো সেই জোড়া-পার্টি (060), কিন্তু এবার দুজন একা এসেছে — ধরো একজন লাল জামা, একজন নীল। সবাই XOR-ভ্যানিশ খেলায় কাটাকাটি করল, রইল শুধু "লাল ⊕ নীল"-এর একটা মিশ্র ছায়া।

এখন তুমি একটা বৈশিষ্ট্য খুঁজে নাও যেটায় লাল আর নীল আলাদা (যেমন "টুপি আছে কি নেই")। সেই বৈশিষ্ট্য দিয়ে পুরো ঘরকে দুই কামরায় ভাগ করো। লাল যাবে এক কামরায়, নীল আরেক কামরায় — আর প্রতিটা জোড়া যেহেতু একই রকম, তারা একসাথে একই কামরায় পড়বে। এবার প্রতি কামরায় আলাদা XOR-খেলা চালাও — প্রতি কামরায় একজন একলা টিকে থাকবে।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

সরাসরি 060 (Odd One Out)-এর XOR-cancel idea-র উপর — সেটাই ধাপ 1। কিন্তু একলা যখন একজন ছিল, পুরো XOR-ই উত্তর দিত; এখন দুজন, তাই XOR দেয় মিশ্রণ a ^ b, আর সেটা ভাঙতে নতুন trick লাগে।

সেই নতুন trick-এ ব্যবহার হয় lowest set bit আলাদা করা (x & (-x)) আর bit দিয়ে check (054)। মানে 061 হলো 060 + একটা partitioning চাল। এই "এক bit দিয়ে দুই দলে ভাগ" চিন্তাটা পরে আরও বড় problem-এ ফিরবে।

ভেতরের অঙ্ক¶

দুই ধাপের idea, দুটোই XOR-ভিত্তিক:

ধাপ 1: পুরো array XOR করো। জোড়াগুলো কাটবে (060-এর মতো), থাকবে xor_all = a ^ b (দুই unique সংখ্যা)। কিন্তু এটা মিশ্রিত — আলাদা করতে হবে।

ধাপ 2: xor_all-এর যেকোনো একটা set bit বেছে নাও। সেই bit যেখানে 1, মানে ওই position-এ a আর b আলাদা (একটায় 1, অন্যটায় 0)। এখন সেই bit দিয়ে পুরো array-কে দুই দলে ভাগ করো — যাদের ওই bit 1 এক দলে, 0 অন্য দলে। তাহলে a আর b আলাদা দলে পড়বে, আর প্রতিটা জোড়া একই দলে (দুজনের bit একই)। দুই দলে আলাদা XOR → দুটো উত্তর।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

XOR-partition না জানলে, hash map দিয়ে count রাখা স্বাভাবিক — যাদের count 1 তাদের তুলে নাও:

Python

def two_unique_brute(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    return [x for x, c in count.items() if c == 1]

কাজ করে — গুনে, count 1 যাদের তারা উত্তর। কিন্তু O(n) extra space (পুরো dictionary)।

কোথায় বেশি কাজ হতে পারে¶

আবার সেই গল্প — time ঠিক (O(n)), কিন্তু space O(n)। interview-তে "constant space" চাইলে hash map বাদ।

উদাহরণ

hash map      : O(n) time, O(n) space
XOR partition : O(n) time, O(1) space  (কয়েকটা int)

XOR-partition-এর জাদু: পুরো count টেবিল না রেখে শুধু কয়েকটা accumulator দিয়েই দুটো unique বের করা। এই O(1) space-ই এর আসল মূল্য।

আরও ভালোভাবে ভাবা¶

XOR all → একটা differing bit বের করো → সেই bit দিয়ে দুই দলে XOR:

Python

def two_unique(nums):
    xor_all = 0
    for x in nums:
        xor_all ^= x                # a ^ b

    diff = xor_all & (-xor_all)     # lowest set bit (যেখানে a, b আলাদা)

    a = b = 0
    for x in nums:
        if x & diff:                # এই bit জ্বলা -> দল A
            a ^= x
        else:                       # নাহলে -> দল B
            b ^= x
    return [a, b]

দুটো pass, কয়েকটা int — O(n) time, O(1) space।

ভাবনার পরিবর্তন¶

আসল "আহা!" — a ^ b-এর যেকোনো set bit মানে সেই position-এ a আর b আলাদা; সেই একটা bit-কে "প্রশ্ন" বানিয়ে পুরো array-কে দুই দলে ভাগ করলে a আর b আলাদা দলে পড়ে, আর প্রতিটা জোড়া একই দলে থাকে।

060-এ একজন একলা ছিল, পুরো XOR-ই উত্তর। দুজন হলে XOR মিশিয়ে দেয় — তাই একটা পার্থক্যের জায়গা খুঁজে সেই অনুযায়ী ভাগ করা। মূল চাবি: জোড়ার দুজনের ওই bit একই (তারা একই সংখ্যা), তাই তারা একই দলে; কিন্তু a আর b ওই bit-এ আলাদা, তাই আলাদা দলে। ফলে প্রতি দল আবার "একটা একলা + কিছু জোড়া" — মানে আবার 060! x & (-x) দিয়ে lowest set bit আলাদা করা একটা bonus classic trick।

ছবিতে বোঝা¶

[1, 2, 1, 3, 2, 5] — ধাপ 1, সব XOR:

উদাহরণ

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
= (1^1) ^ (2^2) ^ 3 ^ 5
= 0 ^ 0 ^ 3 ^ 5
= 3 ^ 5 = 6   (0110)   <- a ^ b

ধাপ 2 — xor_all = 6 = 0110-এর lowest set bit বের করি:

উদাহরণ

xor_all = 0 1 1 0
-xor_all= ...1 0 1 0   (two's complement)
AND     = 0 0 1 0  = 2    <- এই bit-এ 3 আর 5 আলাদা

এই bit (মান 2) দিয়ে দুই দলে ভাগ — bit জ্বলা কিনা দেখি:

উদাহরণ

সংখ্যা : bit&2 জ্বলা?   দল
  1    :   0            দল B
  2    :   1            দল A
  1    :   0            দল B
  3    :   1   (0011)   দল A
  2    :   1            দল A
  5    :   0   (0101)   দল B

দল A XOR: 2 ^ 3 ^ 2 = 3
দল B XOR: 1 ^ 1 ^ 5 = 5
উত্তর: [3, 5] ✓

ছোট input-এ ধাপে ধাপে¶

nums = [1, 2, 1, 3, 2, 5]:

ধাপ 1 — xor_all:

x	xor_all
1	1
2	3
1	2
3	1
2	3
5	6

xor_all = 6 = 0110। diff = 6 & (-6) = 2 = 0010।

ধাপ 2 — diff = 2 দিয়ে ভাগ:

x	x & 2	দল	a (A)	b (B)
1	0	B	0	1
2	2	A	2	1
1	0	B	2	0
3	2	A	1	0
2	2	A	3	0
5	0	B	3	5

শেষে a = 3, b = 5 → [3, 5] ✓।

কোড ও ব্যাখ্যা¶

Python¶

Python

def two_unique(nums):
    """ঠিক দুটো সংখ্যা একবার, বাকি দুবার — সেই দুটো XOR-partition দিয়ে খোঁজে।"""
    xor_all = 0
    for x in nums:
        xor_all ^= x                # a ^ b (জোড়া কেটে গেছে)

    diff = xor_all & (-xor_all)     # lowest set bit: এখানে a আর b আলাদা

    a = b = 0
    for x in nums:
        if x & diff:                # bit জ্বলা -> দল A
            a ^= x
        else:                       # bit নেভানো -> দল B
            b ^= x
    return [a, b]


def two_unique_count(nums):
    """একই উত্তর hash map দিয়ে (যাচাইয়ের জন্য)।"""
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    return [x for x, c in count.items() if c == 1]


# --- ছোট test গুলো (সব pass করা উচিত; ক্রম গুরুত্বপূর্ণ নয়, তাই sorted মেলাই) ---
assert sorted(two_unique([1, 2, 1, 3, 2, 5])) == [3, 5]
assert sorted(two_unique([0, 1])) == [0, 1]            # কোনো জোড়া নেই
assert sorted(two_unique([4, 7])) == [4, 7]
assert sorted(two_unique([1, 1, 2, 3])) == [2, 3]
assert sorted(two_unique([8, 8, 9, 0])) == [0, 9]
assert sorted(two_unique([-1, -1, 5, 6])) == [5, 6]    # negative জোড়াও কাটে

# random: কিছু জোড়া + ঠিক দুটো একলা, XOR-partition == hash map
import random
for _ in range(200):
    pairs = [random.randint(0, 50) for _ in range(random.randint(0, 5))]
    arr = pairs + pairs
    u1, u2 = random.sample(range(100, 300), 2)   # পরিসর আলাদা -> সত্যিই একলা
    arr += [u1, u2]
    random.shuffle(arr)
    assert sorted(two_unique(arr)) == sorted([u1, u2])
    assert sorted(two_unique_count(arr)) == sorted([u1, u2])

print(sorted(two_unique([1, 2, 1, 3, 2, 5])))   # [3, 5]
print(sorted(two_unique([0, 1])))               # [0, 1]
print(sorted(two_unique([1, 1, 2, 3])))         # [2, 3]
print("সব test pass!")

কোডের প্রতিটি অংশ¶

উদাহরণ

for x in nums:
    xor_all ^= x

ধাপ 1 — পুরো array XOR। জোড়া কাটে, থাকে a ^ b।

উদাহরণ

diff = xor_all & (-xor_all)

xor_all-এর lowest set bit আলাদা করি (two's complement trick: x & -x)। এই bit-এ a আর b নিশ্চিত আলাদা, কারণ XOR-এ 1 মানে দুজনের bit ভিন্ন।

উদাহরণ

for x in nums:
    if x & diff:
        a ^= x
    else:
        b ^= x

ধাপ 2 — diff bit জ্বলা কিনা দেখে দুই দলে XOR। প্রতি দলে এখন "একটা একলা + কিছু জোড়া", তাই প্রতি দলের XOR সেই দলের একলা সংখ্যা দেয় — একটা a, একটা b।

assert আর random for loop দুই method-কে 200 ক্ষেত্রে মিলিয়ে নিচ্ছে (sorted করে, কারণ ক্রম গুরুত্বপূর্ণ নয়)। সব ঠিক থাকলে সব test pass!।

Output মিলিয়ে দেখা¶

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

উদাহরণ

[3, 5]
[0, 1]
[2, 3]
সব test pass!

প্রথম তিন লাইন তিনটা print(sorted(...)) থেকে: [1,2,1,3,2,5]→[3,5], [0,1]→[0,1], [1,1,2,3]→[2,3]। সব assert (random cross-check loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n) — দুটো pass, প্রতিটা array-র সব element একবার করে ছোঁয়। মোট তবু linear।

অতিরিক্ত জায়গা¶

O(1) — শুধু কয়েকটা int (xor_all, diff, a, b)। hash-map version-এ O(n) লাগত — এখানে constant।

যে ভুলগুলো এড়াতে হবে¶

diff হিসেবে যেকোনো নয়, একটা set bit নেওয়া — xor_all-এর কোনো একটা জ্বলা bit লাগবে; x & -x দিয়ে lowest-টা নেওয়া সবচেয়ে নিরাপদ।
দল ভাগ করতে x & diff ভুল করা — if x & diff (এই bit জ্বলা কিনা); == diff লিখলেও চলে কিন্তু & diff ই যথেষ্ট আর পরিষ্কার।
output ক্রম নিয়ে চিন্তা — [a, b] যেকোনো ক্রমে ঠিক; sorting দরকার নেই (test-এ শুধু মেলানোর জন্য sorted)।
xor_all == 0 ভাবা — দুটো সংখ্যা আলাদা হলে a ^ b != 0, তাই অন্তত একটা set bit থাকবেই; নাহলে তারা সমান হতো (তখন আর "দুটো unique" নয়)।
শর্ত ভুলে যাওয়া — ঠিক দুটো একলা, বাকি সব দুবার — শর্ত না মানলে এই পদ্ধতি ভুল।

শেখা ও পরের অনুশীলন¶

এই ধারণার পরের অনুশীলন¶

LeetCode — Single Number (https://leetcode.com/problems/single-number/) — এর সহজ পূর্বসূরি (একটা unique)।
066 — Maximum XOR Pair (এই repo) — XOR-এর আরও গভীর প্রয়োগ।
LeetCode — Single Number II (https://leetcode.com/problems/single-number-ii/) — প্রতিটা তিনবার, একটা একবার।
Codeforces — XOR-based constructive (https://codeforces.com/problemset) — partition-by-bit চিন্তা CP-তে বারবার আসে।

কৌশলটি মনে রাখুন¶

XOR partition — XOR all দিয়ে a ^ b, তারপর একটা differing bit বেছে array-কে দুই দলে ভাগ করে প্রতি দলে আবার single-number। বড় শিক্ষা: XOR-এর set bit = সেখানে দুজন আলাদা; সেই bit দিয়ে ভাগ করলে দুই unique আলাদা দলে, জোড়ারা একই দলে — দুটো problem-ই আবার 060 হয়ে যায়।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে এক লাইনে: "দুটো একলা সংখ্যা = XOR all (a ^ b) → lowest set bit (x & -x) → সেই bit দিয়ে দুই দলে আলাদা XOR। set bit মানে দুজন আলাদা — তাই ভাগ করলে প্রতি দল আবার single-number।"

পরের ধাপ → 062 — Subset Generation using Bits (এবার bit আর set মিলে যাবে — প্রতিটা সংখ্যা একটা subset)। সম্পর্কিত → 060 — Odd One Out using XOR · 066 — Maximum XOR Pair।

ফিরে দেখা: এই 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"।