Problem link ও উৎস
- **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-এর যমজ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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`। কাজটা হলো — কোন কোন ঘর "জ্বালালে" সংখ্যাটা পাওয়া যায়, সেটা খুঁজে বের করা।
### Input ও output {#6-example-input-and-output}
```text
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 বেরোবে।
### চেনা উদাহরণে বোঝা {#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।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 "নিয়ে খেলতে" শিখবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **place value in base 2**। যেকোনো সংখ্যাকে 2-এর power-এর যোগফল হিসেবে লেখা যায়:
```text
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 বেরিয়ে আসে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রথমে যেটা মাথায় আসে — Python-এর built-in `bin()` ব্যবহার করা:
```python
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 টা হাতে লেখা জরুরি।
```text
bin() দিয়ে : চটজলদি উত্তর, কিন্তু ভেতরটা black box
loop দিয়ে : একটু লম্বা, কিন্তু প্রতিটা bit কোথা থেকে এল দেখা যায়
```
দুটোরই complexity O(log n) — সংখ্যায় যতগুলো bit, ততবার loop।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
আসল "শেখার" সমাধান — repeated division by 2, last bit সংগ্রহ করতে করতে:
```python
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 কাজ করবে।
### ছবিতে বোঝা {#5-visual-explanation}
place value টেবিল দিয়ে দেখো `13` কীভাবে দাঁড়ায়:
```text
place : 8 4 2 1
bit : 1 1 0 1
--- --- --- ---
8 + 4 + 0 + 1 = 13
```
এবার দেখো কীভাবে `% 2` আর `// 2` নিচ থেকে bit গুলো খুলে আনে:
```text
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 করতে হয়।
### ছোট input-এ ধাপে ধাপে {#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` ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
if n == 0:
return "0"
```
Edge case আগে সামলে নিই — `n = 0` হলে loop একবারও চলবে না, তাই হাতে করে `"0"` দিই।
```text
while n > 0:
bits.append(n % 2)
n //= 2
```
এটাই হৃদয়। `n % 2` দেয় last bit (0 বা 1), সেটা list-এ রাখি। তারপর `n //= 2` দিয়ে সেই bit ফেলে দিই (পুরো সংখ্যাকে এক ঘর ডানে সরানো)। `n` 0 না হওয়া পর্যন্ত চলে।
```text
return "".join(str(b) for b in reversed(bits))
```
bit গুলো বেরিয়েছে উল্টো ক্রমে (নিচ থেকে উপরে), তাই `reversed` দিয়ে সোজা করি, প্রতিটা int-কে str বানাই, আর জোড়া লাগাই।
বাকি `assert` লাইনগুলো নিজেদের চেক করছে — শেষের `for` loop টা 0 থেকে 99 পর্যন্ত আমাদের উত্তরকে Python-এর `bin()`-এর সাথে মিলিয়ে নিচ্ছে। সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
1101
101
0
সব test pass!
```
প্রথম তিন লাইন তিনটা `print(to_binary(...))` থেকে: 13 → 1101, 5 → 101, 0 → 0। তার আগের সব `assert` (cross-check loop সহ) চুপচাপ pass করেছে। সবশেষে `সব test pass!` — সব ঠিক।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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:]` করতে হয়।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **054 — Check ith Bit** (এই repo) — পুরো binary না বের করে শুধু একটা নির্দিষ্ট bit পড়া।
- **058 — Count Set Bits** (এই repo) — binary-তে কতগুলো 1 আছে গোনা।
- **LeetCode — Add Binary** (