061 — Find Two Unique Numbers¶

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

Source¶

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, এক ধাপ এগিয়ে)

1. Problem in simple words¶

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

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

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

2. What is the math idea?¶

দুই ধাপের 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 → দুটো উত্তর।

3. Which basic idea does this inherit from?¶

সরাসরি 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-এ ফিরবে।

4. Real-life analogy¶

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

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

5. Visual explanation¶

[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] ✓

6. Example input and 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 মিলিয়ে নেব।)

7. Brute force thinking¶

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

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

8. Why brute force may be slow¶

আবার সেই গল্প — 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-ই এর আসল মূল্য।

9. Better thinking¶

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

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।

10. Thinking tweak¶

আসল "আহা!" — 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।

11. Step-by-step dry run¶

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] ✓।

12. Python solution¶

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!")

13. Line-by-line explanation¶

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

14. Output walkthrough¶

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

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

15. Time complexity¶

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

16. Space complexity¶

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

17. Common mistakes¶

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" নয়)।
শর্ত ভুলে যাওয়া — ঠিক দুটো একলা, বাকি সব দুবার — শর্ত না মানলে এই পদ্ধতি ভুল।

18. Harder problems that inherit this idea¶

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-তে বারবার আসে।

19. Pattern learned¶

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

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "দুটো একলা সংখ্যা = 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"।