064 — Gray Code¶

DP-র ভারী অধ্যায়ের পর একটু হালকা আর সুন্দর কিছু। Gray code হলো এমন একটা সংখ্যা-ক্রম যেখানে পরপর দুটো সংখ্যায় ঠিক একটা bit বদলায় — আর কোনো ঘর নড়ে না। সাধারণ counting-এ 3→4 মানে 011→100 (তিন bit একসাথে বদলায়), কিন্তু Gray code-এ প্রতি ধাপে মাত্র একটা। আর এর formula অবিশ্বাস্য রকম ছোট: n ^ (n >> 1)। Medium, interview-তে "Gray Code"। চলো।

Source¶

Original source: LeetCode — Gray Code
Platform: LeetCode — https://leetcode.com/problems/gray-code/
Topic: Math-based programming fundamentals → Level 4: Bit Manipulation → gray code
Difficulty: Medium
Pattern: n ^ (n >> 1) (binary থেকে gray code রূপান্তর)
Basic idea inherited from: 053 — Binary Representation (bit বোঝা; এখানে XOR দিয়ে ক্রম)

1. Problem in simple words¶

n দেওয়া আছে। তোমাকে 0 থেকে 2^n - 1 পর্যন্ত সংখ্যাগুলোকে এমন একটা ক্রমে সাজাতে হবে যেখানে:

ক্রমটা 0 দিয়ে শুরু হয়
প্রতিটা সংখ্যা একবার করে আসে (মোট 2^n টা)
পরপর দুটো সংখ্যার binary-তে ঠিক একটা bit আলাদা

এই ক্রমকেই বলে Gray code sequence। যেমন n = 2-এর জন্য একটা বৈধ ক্রম:

0 (00) -> 1 (01) -> 3 (11) -> 2 (10)
        ^শেষ bit  ^মাঝের bit ^শেষ bit
প্রতি ধাপে ঠিক একটা bit বদলালো

2. What is the math idea?¶

মূল idea একটা ছোট্ট formula: i-তম Gray code = i ^ (i >> 1)।

কেন কাজ করে? i ^ (i >> 1) মানে — প্রতিটা bit-কে তার ঠিক বাঁ পাশের bit-এর সাথে XOR করা। এতে সাধারণ binary counting-এর সময় যে "carry-র ঢেউ" একসাথে অনেক bit বদলে দিত, সেটা একটা single flip-এ নেমে আসে।

তাই i = 0, 1, 2, ..., 2^n - 1 প্রতিটার জন্য gray(i) = i ^ (i >> 1) বের করলেই একটা বৈধ Gray code ক্রম পাওয়া যায় — পরপর দুটোয় ঠিক একটা bit আলাদা থাকবে।

3. Which basic idea does this inherit from?¶

দাঁড়িয়ে আছে 053 (Binary Representation) আর XOR (057)-এর উপর। Gray code-এর পুরো খেলা bit-position নিয়ে — "কোন ঘর বদলালো" দেখতে হলে binary পড়তে জানা চাই (053)। আর formula-টা XOR-ভিত্তিক (057-এ পরিচয়)।

সরাসরি কোনো পরের problem এর উপর দাঁড়ায় না, কিন্তু এই "carry-র ঢেউ একটা flip-এ নামানো" idea hardware-এ (rotary encoder, Karnaugh map) আর error-correction-এ বিশাল ব্যবহার হয়। এটা bit-চিন্তার একটা সুন্দর, আলাদা শাখা।

4. Real-life analogy¶

ভাবো একটা পুরোনো যান্ত্রিক odometer (গাড়ির মাইল-মিটার) — ঘরগুলো একসাথে ঘোরে। যখন 0999 → 1000 হয়, একসাথে চারটে ঘর বদলায়। সেই মুহূর্তে যদি কেউ মিটার পড়ে, ভুল পড়তে পারে (একটা ঘর হয়তো অর্ধেক ঘুরেছে)।

Gray code এই সমস্যা এড়ায় — এটা এমনভাবে সাজানো যে এক ধাপে শুধু একটা ঘর ঘোরে। তাই rotary sensor (যেটা কোণ মাপে) Gray code ব্যবহার করে — যেকোনো মুহূর্তে পড়লে বড়জোর একটা bit সন্দেহজনক, পুরো সংখ্যা নয়। "এক ধাপে এক সুইচ" — এটাই Gray code-এর মূল সৌন্দর্য আর কাজের জায়গা।

5. Visual explanation¶

gray(i) = i ^ (i >> 1) কীভাবে কাজ করে (i = 6 = 110):

i       = 1 1 0
i >> 1  = 0 1 1
        --- --- ---
XOR     = 1 0 1  = 5    ->  gray(6) = 5

n = 3-এর পুরো Gray code টেবিল:

i : binary -> gray(i) = i ^ (i>>1)
0 :  000   ->  000
1 :  001   ->  001    <- শেষ bit বদলালো
2 :  010   ->  011    <- মাঝের bit বদলালো
3 :  011   ->  010    <- শেষ bit বদলালো
4 :  100   ->  110    <- বাঁ bit বদলালো
5 :  101   ->  111    <- শেষ bit বদলালো
6 :  110   ->  101    <- মাঝের bit বদলালো
7 :  111   ->  100    <- শেষ bit বদলালো

ডান কলামে পরপর দুটো সারি মেলাও — প্রতিবার ঠিক একটা bit আলাদা ✓।

6. Example input and output¶

n   ->  gray code sequence
--------------------------
0   ->  [0]                          (2^0 = 1 টা)
1   ->  [0, 1]                        (00->01? না, 0->1)
2   ->  [0, 1, 3, 2]                  (00, 01, 11, 10)
3   ->  [0, 1, 3, 2, 6, 7, 5, 4]

edge case: n = 0 → ক্রমে শুধু [0] (2^0 = 1 টা সংখ্যা)। প্রতিটা ক্রমে মোট 2^n টা সংখ্যা থাকে, আর শুরু সবসময় 0।

7. Brute force thinking¶

formula না জানলে, backtracking দিয়ে ক্রম বানানো স্বাভাবিক — 0 থেকে শুরু করে প্রতিবার এমন একটা নতুন সংখ্যা খোঁজা যেটা শেষটার থেকে ঠিক একটা bit আলাদা:

def gray_code_brute(n):
    total = 1 << n
    seq = [0]
    used = {0}
    def differs_by_one(a, b):
        return bin(a ^ b).count("1") == 1     # ঠিক একটা bit আলাদা?
    def backtrack():
        if len(seq) == total:
            return True
        for nxt in range(total):
            if nxt not in used and differs_by_one(seq[-1], nxt):
                seq.append(nxt); used.add(nxt)
                if backtrack():
                    return True
                seq.pop(); used.discard(nxt)
        return False
    backtrack()
    return seq

কাজ করে — প্রতি ধাপে এক-bit-আলাদা প্রতিবেশী খুঁজে এগোই, আটকে গেলে পিছিয়ে আসি। কিন্তু search বড় হলে ধীর।

8. Why brute force may be slow¶

backtracking-এ আমরা সম্ভাব্য ক্রম "খুঁজছি" — প্রতি ধাপে সব candidate দেখে, ভুল হলে পিছিয়ে। worst case-এ এটা exponential search হয়ে যেতে পারে।

backtracking : প্রতি ধাপে সব candidate চেষ্টা, fail হলে backtrack (ধীর, জটিল)
formula      : প্রতিটা gray(i) = i ^ (i >> 1), সরাসরি O(1) প্রতিটায়

অথচ গণিতবিদরা অনেক আগেই দেখিয়েছেন i ^ (i >> 1) সবসময় একটা বৈধ ক্রম দেয় — তাই খোঁজার দরকারই নেই, সরাসরি বানানো যায়। এই formula জানাটাই আসল জয়।

9. Better thinking¶

প্রতিটা i-র জন্য i ^ (i >> 1) বের করো — এক loop-এ পুরো ক্রম:

def gray_code(n):
    return [i ^ (i >> 1) for i in range(1 << n)]

2^n টা সংখ্যা, প্রতিটায় একটা shift আর একটা XOR। কোনো search নেই, কোনো backtrack নেই — সরাসরি O(2^n)।

10. Thinking tweak¶

আসল "আহা!" — প্রতিটা bit-কে তার বাঁ-পাশের bit-এর সাথে XOR (i ^ (i >> 1)) করলে binary counting-এর carry-র ঢেউ একটা single flip-এ নেমে আসে; তাই খুঁজে বের না করে সরাসরি গণনা করেই Gray code পাওয়া যায়।

সাধারণ counting-এ 0111 → 1000-এ চারটে bit একসাথে উল্টোয় (carry chain)। কিন্তু i ^ (i >> 1) প্রতিটা bit-কে তার প্রতিবেশীর সাপেক্ষে দেখে — ফলে যে carry-টা অনেক bit বদলাত, সেটা শুধু একটা position-এ পার্থক্য তৈরি করে। এই "XOR with shifted self = neighbor difference" ছবিটাই Gray code-এর প্রাণ। উল্টোটাও আছে (gray → binary), কিন্তু এই দিকটাই বেশি দরকারি।

11. Step-by-step dry run¶

n = 2, প্রতিটা i-র জন্য gray(i) = i ^ (i >> 1):

i	binary	i >> 1	i ^ (i >> 1)	gray	শেষটার থেকে bit বদল
0	00	00	00	0	(শুরু)
1	01	00	01	1	শেষ bit
2	10	01	11	3	মাঝের bit
3	11	01	10	2	শেষ bit

ক্রম: [0, 1, 3, 2]। প্রতি ধাপে ঠিক একটা bit বদলেছে ✓। আর শেষ (2 = 10) থেকে প্রথম (0 = 00)-ও এক bit আলাদা — তাই ক্রমটা "চক্রাকার"-ও।

12. Python solution¶

def gray_code(n):
    """0 থেকে 2^n - 1 পর্যন্ত একটা Gray code ক্রম: gray(i) = i ^ (i >> 1)।"""
    return [i ^ (i >> 1) for i in range(1 << n)]


def differs_by_one(a, b):
    """a আর b-এর binary-তে ঠিক একটা bit আলাদা কিনা।"""
    return bin(a ^ b).count("1") == 1


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert gray_code(0) == [0]
assert gray_code(1) == [0, 1]
assert gray_code(2) == [0, 1, 3, 2]
assert gray_code(3) == [0, 1, 3, 2, 6, 7, 5, 4]

# Gray code-এর তিন শর্ত যাচাই (n = 0..6):
for n in range(0, 7):
    seq = gray_code(n)
    assert len(seq) == (1 << n)               # ঠিক 2^n টা
    assert seq[0] == 0                         # 0 দিয়ে শুরু
    assert sorted(seq) == list(range(1 << n))  # প্রতিটা সংখ্যা একবার করে
    for k in range(1, len(seq)):
        assert differs_by_one(seq[k - 1], seq[k])   # পরপর ঠিক 1 bit বদল
    if n >= 1:
        assert differs_by_one(seq[-1], seq[0])      # চক্রাকার: শেষ-প্রথমও 1 bit

print(gray_code(2))    # [0, 1, 3, 2]
print(gray_code(3))    # [0, 1, 3, 2, 6, 7, 5, 4]
print("সব test pass!")

13. Line-by-line explanation¶

return [i ^ (i >> 1) for i in range(1 << n)]

এটাই হৃদয়। range(1 << n) দেয় 0 থেকে 2^n - 1। প্রতিটা i-র জন্য i >> 1 (এক ঘর ডানে সরানো) বের করে i-এর সাথে XOR করি — এটাই Gray code formula। list comprehension-এ পুরো ক্রম এক লাইনে।

return bin(a ^ b).count("1") == 1

differs_by_one: a ^ b দিয়ে যেসব bit-এ a আর b আলাদা সেগুলো 1 হয়; count("1") == 1 মানে ঠিক একটা bit আলাদা। যাচাইয়ের প্রাণ।

assert লাইন আর for loop Gray code-এর চারটে শর্ত যাচাই করছে: ঠিক 2^n টা, 0 দিয়ে শুরু, প্রতিটা সংখ্যা একবার করে, আর পরপর (এবং শেষ-প্রথম) ঠিক একটা bit বদল। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough¶

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

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

প্রথম দুই লাইন gray_code(2) আর gray_code(3) — 4টা আর 8টা সংখ্যার ক্রম, প্রতিটায় পরপর সংখ্যায় এক bit বদল। সব assert (চারটে শর্তের loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity¶

O(2^n) — 2^n টা সংখ্যার প্রতিটার জন্য একটা shift আর একটা XOR (constant কাজ)। ক্রমের আকার নিজেই 2^n, তাই এর চেয়ে দ্রুত করা সম্ভব নয়।

16. Space complexity¶

O(2^n) — output ক্রমে 2^n টা সংখ্যা রাখতে হয়। শুধু একটা একটা করে generate করলে (store না করলে) auxiliary space O(1)।

17. Common mistakes¶

i >> 1 ভুলে i << 1 লেখা — Gray code-এ চাই ডানে shift (>> 1); বাঁয়ে shift ভুল ক্রম দেবে।
^ কে power ভাবা — XOR হলো ^, power **। 6 ^ 3 = 5 (XOR)।
ক্রম unique মনে করা — একাধিক বৈধ Gray code ক্রম থাকতে পারে; i ^ (i >> 1) একটা standard ক্রম দেয় (LeetCode এটাই accept করে)।
2^n সংখ্যা ভুলে যাওয়া — range(1 << n), range(n) নয়।
n = 0 ভুলে যাওয়া — n = 0 দেয় [0] (2^0 = 1 টা সংখ্যা), খালি list নয়।

18. Harder problems that inherit this idea¶

LeetCode — Gray Code (https://leetcode.com/problems/gray-code/) — এই problem-এরই মূল রূপ।
LeetCode — Circular Permutation in Binary Representation (https://leetcode.com/problems/circular-permutation-in-binary-representation/) — নির্দিষ্ট start থেকে Gray code।
LeetCode — Minimum Number of K Consecutive Bit Flips (https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/) — bit flip চিন্তার আরেক রূপ।

19. Pattern learned¶

Gray code via n ^ (n >> 1) — প্রতিটা সংখ্যাকে তার shifted রূপের সাথে XOR করে এমন ক্রম, যেখানে পরপর সংখ্যায় ঠিক একটা bit বদলায়। বড় শিক্ষা: shifted-self-এর সাথে XOR = neighbor difference; এতে carry-র ঢেউ একটা single flip-এ নামে — খুঁজে নয়, সরাসরি গণনা করেই ক্রম পাওয়া যায়।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Gray code = [i ^ (i >> 1) for i in range(1 << n)]। পরপর সংখ্যায় ঠিক এক bit বদলায়; carry-র ঢেউ এক flip-এ নামে। 'এক ধাপে এক bit বদল' (rotary encoder, K-map) শুনলেই n ^ (n >> 1) মনে করব।"

পরের ধাপ → 065 — AND/OR/XOR Range Tricks (পরপর সংখ্যার range-এ AND/OR/XOR — common prefix-এর জাদু)। সম্পর্কিত → 053 — Binary Representation।

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