053 — Binary Representation

এই note দিয়ে Level 4 শুরু — bit manipulation-এর একদম বর্ণমালা। যেকোনো integer আসলে 0 আর 1-এর একটা সারি, আর সেই সারিটা কীভাবে বের করতে হয় সেটাই আজকের গল্প। Level 0-এ যে digit ভাঙা শিখেছিলে (% 10, // 10), আজ ঠিক সেই idea 2-এর ঘরে নিয়ে যাব। "vule gesi" — সমস্যা নেই, এই note ধরে ধরে আবার বসে যাবে।

Source

• Original source: Classic exercise (base conversion — প্রতিটা ভাষার শুরুর exercise)
• Platform: Classic exercise / — (specific judge নেই)
• Topic: Math-based programming fundamentals → Level 4: Bit Manipulation → binary representation
• Difficulty: Easy
• Pattern: base conversion (place value টেবিল)
• Basic idea inherited from: — (এটাই এই level-এর শিকড়; Level 0-এর digit extraction-এর যমজ)

1. Problem in simple words

একটা non-negative integer n দেওয়া আছে। তোমাকে বের করতে হবে এর binary representation — মানে শুধু 0 আর 1 দিয়ে লেখা রূপটা।

যেমন:

• 13 → 1101
• 5 → 101
• 0 → 0

Decimal-এ আমরা 10-এর ঘর গুনি (একক, দশক, শতক)। Binary-তে গুনি 2-এর ঘর: 8 4 2 1। কাজটা হলো — কোন কোন ঘর "জ্বালালে" সংখ্যাটা পাওয়া যায়, সেটা খুঁজে বের করা।

2. What is the math idea?

মূল idea হলো place value in base 2। যেকোনো সংখ্যাকে 2-এর power-এর যোগফল হিসেবে লেখা যায়:

13 = 8 + 4 + 1 = 1×8 + 1×4 + 0×2 + 1×1

আর কোন ঘরে 1 বসবে সেটা বের করার নিয়ম একদম digit extraction-এর মতো — শুধু 10-এর জায়গায় 2:

• n % 2 → last bit (একদম ডানের ঘর)
• n // 2 → সেই bit ফেলে দিয়ে বাকিটা

বারবার এই দুটো করলে নিচ থেকে উপরে এক-একটা bit বেরিয়ে আসে।

3. Which basic idea does this inherit from?

এটা Level 4-এর প্রথম problem, তাই এই level-এর ভেতরে আগে কিছু নেই (inherited from: —)।

কিন্তু এটা শূন্য থেকে আসেনি — এটা সরাসরি Level 0-এর digit extraction-এর যমজ ভাই। সেখানে তুমি % 10 দিয়ে last digit ছুঁতে আর // 10 দিয়ে সেটা ফেলতে। এখানে ঠিক একই নাচ, কিন্তু base 2-তে: % 2 আর // 2।

এই 053-এর উপর দাঁড়িয়ে গজাবে পুরো level:

• 054 (Check ith Bit) — কোনো একটা নির্দিষ্ট bit জ্বলছে কিনা দেখা
• 060 (Odd One Out) — bit দিয়ে XOR-এর খেলা
• 064 (Gray Code) — bit pattern-এর সুন্দর ক্রম

মানে আজ binary "পড়তে" শিখলে, কাল binary "নিয়ে খেলতে" শিখবে।

4. Real-life analogy

ভাবো তোমার কাছে কতগুলো ওজন আছে — 1, 2, 4, 8, 16, ... কেজি, প্রতিটা ঠিক একটা করে। তোমাকে দাঁড়িপাল্লায় 13 কেজি মাপতে হবে।

তুমি বড় ওজন থেকে শুরু করবে: 8 লাগবে? হ্যাঁ (বাকি 5)। 4 লাগবে? হ্যাঁ (বাকি 1)। 2 লাগবে? না (1 < 2)। 1 লাগবে? হ্যাঁ (বাকি 0)।

যেগুলো নিলে সেখানে 1, যেগুলো নিলে না সেখানে 0 → 1101। প্রতিটা ওজন একটা bit, আর "নিলাম কি নিলাম না" — সেটাই 0/1।

5. Visual explanation

place value টেবিল দিয়ে দেখো 13 কীভাবে দাঁড়ায়:

place :   8   4   2   1
bit   :   1   1   0   1
        --- --- --- ---
        8 + 4 + 0 + 1  =  13

এবার দেখো কীভাবে % 2 আর // 2 নিচ থেকে bit গুলো খুলে আনে:

n = 13 -> 13 % 2 = 1   n হয় 6     bits: 1
n = 6  -> 6  % 2 = 0   n হয় 3     bits: 1 0
n = 3  -> 3  % 2 = 1   n হয় 1     bits: 1 0 1
n = 1  -> 1  % 2 = 1   n হয় 0     bits: 1 0 1 1
                                   থামো (n = 0)

উল্টে দাও  ->  1 1 0 1   ✓

লক্ষ করো — bit গুলো বের হয় উল্টো ক্রমে (last bit আগে)। তাই শেষে list-টা reverse করতে হয়।

6. Example input and output

input  ->  output
-----------------
  13   ->  "1101"
   5   ->  "101"
   1   ->  "1"
   0   ->  "0"        (edge case: শূন্যের জন্য একটা 0)
   2   ->  "10"
   8   ->  "1000"     (শুধু একটা ঘর জ্বলা — power of two)

সবচেয়ে গুরুত্বপূর্ণ edge case হলো n = 0 — loop একবারও চলবে না, তাই হাতে করে "0" ফেরত দিতে হবে, নাহলে খালি string বেরোবে।

7. Brute force thinking

প্রথমে যেটা মাথায় আসে — Python-এর built-in bin() ব্যবহার করা:

def to_binary_builtin(n):
    return bin(n)[2:]      # bin(13) = '0b1101', তাই [2:] দিয়ে '0b' ফেলে দিই

এটা ঠিক উত্তর দেয়, কিন্তু এতে আসল mechanism-টা লুকিয়ে থাকে। তাই শেখার জন্য আমরা loop দিয়ে নিজে বানাব — তাতে % 2 আর // 2-এর নাচটা চোখে দেখা যায়।

8. Why brute force may be slow

এখানে আসলে "slow" ব্যাপারটা নয় — bin() যথেষ্ট দ্রুত (O(log n))। সমস্যা হলো শেখা।

bin() দিয়ে করলে তুমি জানো না কীভাবে bit বের হয়। কিন্তু 054, 055, 058 — পরের প্রায় সব problem-এ তোমাকে bit নিয়ে নিজে কাজ করতে হবে। তাই অন্তত একবার loop টা হাতে লেখা জরুরি।

bin() দিয়ে : চটজলদি উত্তর, কিন্তু ভেতরটা black box
loop দিয়ে  : একটু লম্বা, কিন্তু প্রতিটা bit কোথা থেকে এল দেখা যায়

দুটোরই complexity O(log n) — সংখ্যায় যতগুলো bit, ততবার loop।

9. Better thinking

আসল "শেখার" সমাধান — repeated division by 2, last bit সংগ্রহ করতে করতে:

def to_binary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        bits.append(n % 2)
        n //= 2
    return "".join(str(b) for b in reversed(bits))

প্রতি step-এ একটা bit, তাই মোট step = সংখ্যার bit-সংখ্যা = O(log n)। আর এটা তোমাকে সেই foundation দেয় যার উপর পুরো level দাঁড়াবে।

10. Thinking tweak

আসল "আহা!" মুহূর্ত — binary বের করা আর decimal-এ digit ভাঙা একই কাজ, শুধু base বদলেছে।

• Decimal digit: n % 10 দিয়ে last digit, n // 10 দিয়ে বাকি
• Binary bit: n % 2 দিয়ে last bit, n // 2 দিয়ে বাকি

একই algorithm, একই দুটো লাইন — শুধু 10-কে 2 বানিয়ে দাও। নতুন কিছু শিখছ না, পুরোনো জিনিস নতুন base-এ চালাচ্ছ। এই দৃষ্টিটা থাকলে base 8, base 16 — যেকোনো base-এ একই trick কাজ করবে।

11. Step-by-step dry run

চলো n = 13 ধীরে চালাই:

step	n (শুরুতে)	n % 2 (bit)	n // 2 (নতুন n)	bits
1	13	1	6	[1]
2	6	0	3	[1, 0]
3	3	1	1	[1, 0, 1]
4	1	1	0	[1, 0, 1, 1]
—	0	loop থামল	—	[1, 0, 1, 1]

এবার bits reverse করো: [1, 1, 0, 1] → string "1101"। মিলিয়ে দেখো: 8 + 4 + 0 + 1 = 13 ✓।

12. Python solution

def to_binary(n):
    """non-negative int n-এর binary string ফেরত দেয়।"""
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        bits.append(n % 2)      # last bit
        n //= 2                 # সেই bit ফেলে দাও
    return "".join(str(b) for b in reversed(bits))


def to_binary_list(n):
    """একই কাজ, কিন্তু bit-এর list ফেরত দেয় (পরের problem-এ কাজে লাগবে)।"""
    if n == 0:
        return [0]
    bits = []
    while n > 0:
        bits.append(n % 2)
        n //= 2
    return bits[::-1]


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert to_binary(13) == "1101"
assert to_binary(5) == "101"
assert to_binary(1) == "1"
assert to_binary(0) == "0"          # edge case: শূন্য
assert to_binary(2) == "10"
assert to_binary(8) == "1000"
assert to_binary(255) == "11111111"
assert to_binary_list(13) == [1, 1, 0, 1]
assert to_binary_list(0) == [0]

# Python-এর built-in-এর সাথে মিলিয়ে দেখা (cross-check)
for k in range(0, 100):
    assert to_binary(k) == bin(k)[2:]

print(to_binary(13))    # 1101
print(to_binary(5))     # 101
print(to_binary(0))     # 0
print("সব test pass!")

13. Line-by-line explanation

if n == 0:
    return "0"

Edge case আগে সামলে নিই — n = 0 হলে loop একবারও চলবে না, তাই হাতে করে "0" দিই।

while n > 0:
    bits.append(n % 2)
    n //= 2

এটাই হৃদয়। n % 2 দেয় last bit (0 বা 1), সেটা list-এ রাখি। তারপর n //= 2 দিয়ে সেই bit ফেলে দিই (পুরো সংখ্যাকে এক ঘর ডানে সরানো)। n 0 না হওয়া পর্যন্ত চলে।

return "".join(str(b) for b in reversed(bits))

bit গুলো বেরিয়েছে উল্টো ক্রমে (নিচ থেকে উপরে), তাই reversed দিয়ে সোজা করি, প্রতিটা int-কে str বানাই, আর জোড়া লাগাই।

বাকি assert লাইনগুলো নিজেদের চেক করছে — শেষের for loop টা 0 থেকে 99 পর্যন্ত আমাদের উত্তরকে Python-এর bin()-এর সাথে মিলিয়ে নিচ্ছে। সব ঠিক থাকলে শেষে সব test pass! ছাপে।

14. Output walkthrough

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

1101
101
0
সব test pass!

প্রথম তিন লাইন তিনটা print(to_binary(...)) থেকে: 13 → 1101, 5 → 101, 0 → 0। তার আগের সব assert (cross-check loop সহ) চুপচাপ pass করেছে। সবশেষে সব test pass! — সব ঠিক।

15. Time complexity

O(log n) — প্রতি step-এ n 2 দিয়ে ভাগ হচ্ছে, তাই step-সংখ্যা = সংখ্যার bit-সংখ্যা ≈ log₂(n)। যেমন 13-এর জন্য 4 step, 255-এর জন্য 8 step।

16. Space complexity

O(log n) — bits list-এ ঠিক ততগুলো element রাখছি যতগুলো bit আছে, মানে log₂(n)-এর সমান। output string-ও একই আকারের।

17. Common mistakes

1. n = 0 ভুলে যাওয়া — loop একবারও চলবে না, তখন খালি string বেরোয়। আলাদা করে "0" দিতে হবে।
2. reverse করতে ভুলে যাওয়া — bit বের হয় উল্টো ক্রমে। reverse না করলে 13 দেখাবে "1011" (ভুল)।
3. / আর // গুলিয়ে ফেলা — Python-এ 13 / 2 = 6.5 (float)। integer division // লাগবে, নাহলে % 2 ভেঙে যাবে।
4. negative সংখ্যা ধরে নেওয়া — এই simple version শুধু non-negative-এর জন্য। negative-এর binary (two's complement) আলাদা গল্প।
5. bin()-এর '0b' prefix ভুলে যাওয়া — bin(13) দেয় '0b1101', খাঁটি bit চাইলে [2:] করতে হয়।

18. Harder problems that inherit this idea

• 054 — Check ith Bit (এই repo) — পুরো binary না বের করে শুধু একটা নির্দিষ্ট bit পড়া।
• 058 — Count Set Bits (এই repo) — binary-তে কতগুলো 1 আছে গোনা।
• LeetCode — Add Binary (https://leetcode.com/problems/add-binary/) — দুটো binary string যোগ করা; এই base-2 চিন্তা সরাসরি কাজে লাগে।
• LeetCode — Number of 1 Bits (https://leetcode.com/problems/number-of-1-bits/) — bit গোনার classic।

19. Pattern learned

Base conversion via repeated division — % base দিয়ে last digit/bit, // base দিয়ে বাকিটা, তারপর reverse। base 2-তে এটাই binary representation। বড় শিক্ষা: decimal digit ভাঙা আর binary bit ভাঙা একই algorithm, শুধু base বদলায়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "binary বের করা = % 2 আর // 2 দিয়ে digit extraction, শেষে reverse; n = 0 আলাদা করে সামলাও। এটাই পুরো bit-জগতের বর্ণমালা।"

পরের ধাপ → 054 — Check ith Bit (পুরো binary না বের করে শুধু একটা bit পড়ব)। সম্পর্কিত → 060 — Odd One Out using XOR।

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