Problem link ও উৎস
- **Original source:** Classic exercise (bit primitive — set)
- **Platform:** Classic exercise / — (specific judge নেই)
- **Topic:** Math-based programming fundamentals → Level 4: Bit Manipulation → bit primitives
- **Difficulty:** Easy
- **Pattern:** mask OR (`|` দিয়ে নির্দিষ্ট bit জ্বালানো)
- **Basic idea inherited from:** 054 — Check ith Bit (একই `mask = 1 << i`, operator বদল)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer `n` আর index `i` দেওয়া আছে। তোমাকে `n`-এর `i`-তম bit-টা **জ্বালিয়ে** (1 বানিয়ে) নতুন সংখ্যাটা ফেরত দিতে হবে।
- bit আগে থেকেই 1 হলে → কিছু বদলাবে না
- bit 0 হলে → সেটা 1 হয়ে যাবে, সংখ্যা বাড়বে
যেমন `n = 13 = 1101`, `i = 1`:
```text
1101 -> ঘর 1 জ্বালাও -> 1111 = 15
```
### Input ও output {#6-example-input-and-output}
```text
n, i -> output
------------------
13, 1 -> 15 (1101 -> 1111)
13, 0 -> 13 (ঘর 0 আগেই জ্বলা -> অপরিবর্তিত)
13, 2 -> 13 (ঘর 2 আগেই জ্বলা)
0, 3 -> 8 (0000 -> 1000)
0, 0 -> 1 (0 -> 1)
5, 1 -> 7 (101 -> 111)
8, 0 -> 9 (1000 -> 1001)
```
edge case: যে ঘর **আগে থেকেই জ্বলা**, সেখানে set করলে সংখ্যা বদলায় না — কোনো error নয়, শুধু "already on"।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
সেই সুইচবোর্ডে ফিরি। তোমার হাতে এমন একটা magic switch (mask) যেটা শুধু `i` নম্বর light-এ লাগানো। তুমি সেটা **জোর করে on** করে দিলে।
- light আগে on ছিল? on-ই থাকল, কিছু বদলালো না।
- light off ছিল? এবার জ্বলে উঠল।
বাকি কোনো light-এ তোমার হাত পড়েনি — তারা যেমন ছিল তেমনই। এই "জোর করে on" করাই `| mask`।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **054 (Check ith Bit)**-এর ভাই। 054-এ একই `mask = 1 << i` বানিয়ে `&` দিয়ে bit **পড়েছিলে**; এখানে সেই একই mask, কিন্তু `|` দিয়ে bit **জ্বালাচ্ছ**।
পুরো পরিবারটা দেখো — সবার মূলে এক টর্চলাইট, শুধু operator আলাদা:
- **054 check:** `n & mask` — পড়া
- **055 set:** `n | mask` — জ্বালানো (আজ)
- **056 clear:** `n & ~mask` — নেভানো
- **057 toggle:** `n ^ mask` — উল্টানো
একটা বুঝলে চারটাই বোঝা — শুধু operator-এর স্বভাব মনে রাখো।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **OR দিয়ে force-1**। `|` operator-এর স্বভাব: `bit | 1 = 1` সবসময় (জোর করে জ্বালায়), আর `bit | 0 = bit` (অপরিবর্তিত রাখে)।
তাই mask `1 << i` (শুধু `i`-তম ঘরে 1) দিয়ে OR করলে:
- target ঘরে → জোর করে 1 (set!)
- বাকি সব ঘরে mask-এ 0, তাই `bit | 0 = bit` → অপরিবর্তিত
মানে শুধু একটা ঘর জ্বলে, বাকি কেউ টের পায় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
mask না জানলে, প্রথমে binary list বানিয়ে (053-এর মতো) ওই index-এ জোর করে 1 বসিয়ে আবার সংখ্যায় ফেরা মাথায় আসে:
```python
def set_bit_brute(n, i):
bits = []
while n > 0:
bits.append(n % 2)
n //= 2
while len(bits) <= i: # ঘর i না থাকলে 0 দিয়ে বাড়াও
bits.append(0)
bits[i] = 1 # জোর করে 1
value = 0
for k in range(len(bits)): # আবার সংখ্যায় রূপান্তর
value += bits[k] * (1 << k)
return value
```
কাজ করে — পুরো list ভেঙে, ঠিক জায়গায় 1 বসিয়ে, আবার জোড়া লাগাচ্ছি। কিন্তু এক ঘর জ্বালাতে এত খাটুনি!
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
brute force-এ পুরো binary list বানাচ্ছি, ঘর কম পড়লে বাড়াচ্ছি, আবার পুরো list থেকে সংখ্যা গড়ছি — সবই O(log n)। অথচ দরকার ছিল **একটা** OR।
```text
brute : list ভাঙো -> index-এ 1 বসাও -> আবার সংখ্যা গড়ো (O(log n))
smart : n | (1 << i) (O(1))
```
এক bit জ্বালানোর জন্য পুরো সংখ্যা ভাঙা-গড়া — খাঁটি অপচয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
mask দিয়ে এক ধাপে OR করো:
```python
def set_bit(n, i):
return n | (1 << i)
```
কোনো loop নেই, list নেই — একটা shift, একটা OR। O(1), `n` যত বড়ই হোক। target ঘর জ্বলে, বাকি কেউ অক্ষত — কারণ `bit | 0 = bit`।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **`|` শুধু জ্বালাতে পারে, নেভাতে পারে না; তাই mask-এর 0-গুলো সব ঘরকে "ছুঁয়েও ছাড়ে"।**
`1 << i`-এ শুধু target ঘরে 1, বাকি সব 0। OR-এ যেখানে mask-এ 0 সেখানে original অপরিবর্তিত (`bit | 0 = bit`), আর যেখানে mask-এ 1 (একমাত্র target) সেখানে জোর করে 1। ফল: ঠিক একটা ঘর জ্বলে, পাশের কেউ টের পায় না। 054-এর check-এ একই mask `&`-এর সাথে পড়ত; আজ `|`-এর সাথে লেখে। mask এক, operator-এর স্বভাব আলাদা — এটাই পুরো খেলা।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 13`, `i = 1` — set:
```text
n = 1 1 0 1 (13)
mask = 0 0 1 0 (1 << 1)
--- --- --- ---
n | mask= 1 1 1 1 (15) ঘর 1 জ্বলে উঠল, বাকি অক্ষত ✓
```
এখন এমন ঘর যেটা আগেই জ্বলা (`i = 0`) — কিছু বদলায় না:
```text
n = 1 1 0 1
mask = 0 0 0 1 (1 << 0)
--- --- --- ---
n | mask= 1 1 0 1 (13) ঘর 0 আগেই 1 ছিল -> অপরিবর্তিত
```
লক্ষ করো — `|` কখনো কোনো bit নেভায় না, শুধু জ্বালাতে পারে (বা একই রাখে)।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`n = 13`, `i = 1`:
| step | কাজ | মান (4-bit) |
| --- | --- | --- |
| 1 | শুরু: n | 1101 |
| 2 | mask = 1 << 1 | 0010 |
| 3 | n \| mask | 1111 |
| 4 | দশমিকে | 15 |
উত্তর: `15`। এখন `n = 13, i = 0` (আগেই জ্বলা ঘর):
| step | কাজ | মান (4-bit) |
| --- | --- | --- |
| 1 | n | 1101 |
| 2 | mask = 1 << 0 | 0001 |
| 3 | n \| mask | 1101 |
| 4 | দশমিকে | 13 |
ঘর 0 আগেই 1 ছিল, তাই কিছু বদলায়নি → `13`।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def set_bit(n, i):
"""n-এর i-তম bit জ্বালিয়ে (1 বানিয়ে) নতুন সংখ্যা ফেরত দেয়।"""
return n | (1 << i)
def is_set(n, i):
"""যাচাইয়ের জন্য: bit জ্বলা কিনা (054-এর check)।"""
return (n & (1 << i)) != 0
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert set_bit(13, 1) == 15 # 1101 -> 1111
assert set_bit(13, 0) == 13 # আগেই জ্বলা -> অপরিবর্তিত
assert set_bit(13, 2) == 13 # আগেই জ্বলা
assert set_bit(0, 3) == 8 # 0000 -> 1000
assert set_bit(0, 0) == 1 # 0 -> 1
assert set_bit(5, 1) == 7 # 101 -> 111
assert set_bit(8, 0) == 9 # 1000 -> 1001
# set করার পর সেই bit সবসময় জ্বলা থাকবে — যাচাই
for n in range(0, 64):
for i in range(0, 8):
result = set_bit(n, i)
assert is_set(result, i) is True # set করার পর জ্বলা
assert result == n or result == n + (1 << i) # বাড়ে অথবা একই
print(set_bit(13, 1)) # 15
print(set_bit(13, 0)) # 13
print(set_bit(0, 3)) # 8
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
return n | (1 << i)
```
এটাই হৃদয়। `1 << i` বানায় mask — শুধু `i`-তম ঘরে 1। `n | mask`: target ঘরে জোর করে 1 (set), আর বাকি ঘরে mask-এ 0 থাকায় `bit | 0 = bit` → অপরিবর্তিত। তাই ঠিক একটা ঘর জ্বলে।
```text
return (n & (1 << i)) != 0
```
এটা 054-এর check — শুধু যাচাইয়ের জন্য রাখা, যাতে test-এ "set করার পর সত্যিই জ্বলা" নিশ্চিত করা যায়।
`assert` লাইনগুলো আর nested `for` loop নিজেরা যাচাই করছে: set করার পর bit সবসময় জ্বলা, আর সংখ্যা হয় অপরিবর্তিত (আগেই জ্বলা থাকলে) নয়তো ঠিক `1 << i` বাড়ে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
15
13
8
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: (13,1)→15, (13,0)→13 (অপরিবর্তিত), (0,3)→8। সব `assert` (যাচাই loop সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — একটা shift, একটা OR। `n`-এর আকারে কাজ বাড়ে না; পুরো সংখ্যা না ভেঙে শুধু একটা ঘর জ্বালাচ্ছি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — কোনো list বা array লাগছে না; কয়েকটা int মাত্র।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`|` আর `or` গুলিয়ে ফেলা** — bitwise কাজে সবসময় `|`, logical `or` নয়।
2. **`1 << i` ভুলে `i << 1` লেখা** — `1 << 3 = 8` (mask), `3 << 1 = 6` (double)।
3. **set আর toggle গুলিয়ে ফেলা** — set (`|`) আগেই জ্বলা bit-কে জ্বালাই রাখে; toggle (`^`) সেটাকে নিভিয়ে দিত! দুটো আলাদা।
4. **Precedence ফাঁদ** — অন্য expression-এর সাথে মেশালে bracket দাও: `(n | (1 << i))`।
5. **Negative i বা বিশাল i** — `1 << -1` ValueError; খুব বড় i memory খাবে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **056 — Clear ith Bit** / **057 — Toggle ith Bit** (এই repo) — একই mask, ভিন্ন operator।
- **062 — Subset Generation using Bits** (এই repo) — element নেওয়া মানে সেই bit set করা।
- **LeetCode — Single Number** (