Problem link ও উৎস
- **Original source:** Classic exercise (bit primitive — toggle)
- **Platform:** Classic exercise / — (specific judge নেই)
- **Topic:** Math-based programming fundamentals → Level 4: Bit Manipulation → bit primitives
- **Difficulty:** Easy
- **Pattern:** mask ^ (XOR দিয়ে নির্দিষ্ট 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 **উল্টে** (flip করে) নতুন সংখ্যা ফেরত দিতে হবে।
- bit 1 হলে → 0 হয়ে যাবে
- bit 0 হলে → 1 হয়ে যাবে
যেমন `n = 13 = 1101`:
```text
i = 1 (নেভানো ছিল) -> 1111 = 15 (জ্বলে উঠল)
i = 0 (জ্বলা ছিল) -> 1100 = 12 (নিভে গেল)
```
একই operation দুবার করলে আবার আগের জায়গায় ফিরে আসে — এটাই toggle-এর মজা।
### Input ও output {#6-example-input-and-output}
```text
n, i -> output
------------------
13, 1 -> 15 (1101 -> 1111, ঘর 1 জ্বলল)
13, 0 -> 12 (1101 -> 1100, ঘর 0 নিভল)
13, 2 -> 9 (1101 -> 1001, ঘর 2 নিভল)
0, 3 -> 8 (0000 -> 1000)
8, 3 -> 0 (1000 -> 0000)
5, 0 -> 4 (101 -> 100)
5, 1 -> 7 (101 -> 111)
```
toggle-এ আলাদা edge case নেই — যেকোনো bit সবসময় উল্টোয়। মূল property: **দুবার toggle = মূল সংখ্যা**।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
সুইচবোর্ডে সেই magic switch। কিন্তু এবার তুমি জানোই না light টা এখন on না off — তুমি শুধু **toggle button** চাপলে। on থাকলে off হবে, off থাকলে on হবে।
আর মজাটা: একই toggle button **দুবার** চাপলে light আবার আগের অবস্থায় — কারণ দুটো flip একে অপরকে বাতিল করে। এই "যা আছে তার উল্টো" আর "দুবার করলে আগের জায়গায়" — দুটোই XOR-এর গভীর ধর্ম, যা পরে বড় problem-এ কাজে লাগবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দাঁড়িয়ে আছে **054 (Check ith Bit)**-এর উপর — সেই একই `mask = 1 << i`। এই note দিয়ে চারটে primitive-ই সম্পূর্ণ হলো:
- **054 check:** `n & mask` — পড়া
- **055 set:** `n | mask` — জোর করে 1
- **056 clear:** `n & ~mask` — জোর করে 0
- **057 toggle:** `n ^ mask` — উল্টানো (আজ)
toggle-কে বলতে পারো সবচেয়ে "নিরপেক্ষ" ভাই — set জানে শুধু জ্বালাতে, clear জানে শুধু নেভাতে, কিন্তু toggle দুটোই করে, যা আছে তার উপর নির্ভর করে।
আর এই `^` operator-টাই পরে 060 (Single Number), 061 (Two Unique), 066 (Max XOR)-এ আসল তারকা হয়ে উঠবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **XOR দিয়ে flip**। `^` (XOR)-এর স্বভাব: `bit ^ 1 = উল্টো bit` (0↔1 flip), আর `bit ^ 0 = bit` (অপরিবর্তিত)।
তাই mask `1 << i` (শুধু target-এ 1) দিয়ে XOR করলে:
- target ঘরে → `^ 1` → flip
- বাকি সব ঘরে mask-এ 0, তাই `^ 0` → অপরিবর্তিত
মানে ঠিক একটা ঘর উল্টে যায়, বাকি কেউ নড়ে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
mask না জানলে, আগে bit-টা পড়ে (054) তারপর উল্টোটা বসানো মাথায় আসে — অর্থাৎ if-else দিয়ে set বা clear বেছে নেওয়া:
```python
def toggle_bit_brute(n, i):
if (n >> i) & 1: # bit জ্বলা?
return n & ~(1 << i) # তাহলে নেভাও (clear)
else:
return n | (1 << i) # নাহলে জ্বালাও (set)
```
কাজ করে — আগে অবস্থা দেখি, তারপর উল্টো কাজ করি। কিন্তু একটা if-else লাগছে, যেটা XOR দিয়ে একদম এড়ানো যায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এটা ঠিক "slow" নয় (দুটোই O(1)), বরং **অপ্রয়োজনীয় branch**। আগে bit পড়া, তারপর if-else দিয়ে দুটো ভিন্ন রাস্তা — অথচ XOR এক লাইনে দুই ক্ষেত্রই সামলায়।
```text
brute : bit পড়ো -> if জ্বলা তো clear, নাহলে set (branch লাগে)
smart : n ^ (1 << i) (কোনো branch নেই)
```
XOR-এর সৌন্দর্য — সে নিজেই জানে কোনটা flip করতে হবে, আমাদের জিজ্ঞেস করতে হয় না।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
mask দিয়ে এক ধাপে XOR করো:
```python
def toggle_bit(n, i):
return n ^ (1 << i)
```
কোনো if নেই, কোনো branch নেই — একটা shift, একটা XOR। O(1)। target ঘর উল্টোয়, বাকি অক্ষত (কারণ `bit ^ 0 = bit`)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **`^ 1` মানে flip, `^ 0` মানে অপরিবর্তিত; তাই XOR নিজেই "যা আছে তার উল্টো" করে দেয়, আমাদের অবস্থা জানতেই হয় না।**
set/clear-এ আমাদের জানতে হতো কী চাই (1 না 0)। কিন্তু toggle-এ চাই "যা-ই থাক, উল্টে দাও" — আর এটাই XOR-এর সহজাত স্বভাব। mask-এর target ঘরে 1 থাকায় সেখানে flip, বাকি ঘরে 0 থাকায় অপরিবর্তিত। বোনাস insight: `a ^ a = 0` — তাই দুবার toggle করলে আগের জায়গায়। এই দুই ধর্ম (`^ 1` flip, `a ^ a = 0`) পরে Single Number-এ পুরো problem solve করে দেবে।
### ছবিতে বোঝা {#5-visual-explanation}
`n = 13`, প্রথমে `i = 1` (নেভানো → জ্বলবে):
```text
n = 1 1 0 1 (13)
mask = 0 0 1 0 (1 << 1)
--- --- --- ---
n ^ mask= 1 1 1 1 (15) ঘর 1 flip: 0 -> 1 ✓
```
এখন `i = 0` (জ্বলা → নিভবে):
```text
n = 1 1 0 1
mask = 0 0 0 1 (1 << 0)
--- --- --- ---
n ^ mask= 1 1 0 0 (12) ঘর 0 flip: 1 -> 0 ✓
```
দুবার toggle করলে ফিরে আসে:
```text
13 ^ 0010 = 15 -> 15 ^ 0010 = 13 (আবার মূল!)
```
### ছোট 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`। এখন আবার toggle করি (`15, i = 1`):
| step | কাজ | মান (4-bit) |
| --- | --- | --- |
| 1 | n | 1111 |
| 2 | mask = 1 << 1 | 0010 |
| 3 | n ^ mask | 1101 |
| 4 | দশমিকে | 13 |
আবার 13 — দুবার toggle মূলে ফিরিয়ে আনল ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def toggle_bit(n, i):
"""n-এর i-তম bit উল্টে (flip করে) নতুন সংখ্যা ফেরত দেয়।"""
return n ^ (1 << i)
def is_set(n, i):
"""যাচাইয়ের জন্য: bit জ্বলা কিনা (054-এর check)।"""
return (n & (1 << i)) != 0
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert toggle_bit(13, 1) == 15 # 1101 -> 1111
assert toggle_bit(13, 0) == 12 # 1101 -> 1100
assert toggle_bit(13, 2) == 9 # 1101 -> 1001
assert toggle_bit(0, 3) == 8 # 0000 -> 1000
assert toggle_bit(8, 3) == 0 # 1000 -> 0000
assert toggle_bit(5, 0) == 4 # 101 -> 100
assert toggle_bit(5, 1) == 7 # 101 -> 111
# মূল property: দুবার toggle = মূল সংখ্যা; আর প্রতিবার bit flip হয়
for n in range(0, 64):
for i in range(0, 8):
once = toggle_bit(n, i)
assert is_set(once, i) == (not is_set(n, i)) # bit সত্যিই flip
assert toggle_bit(once, i) == n # দুবার -> মূল
print(toggle_bit(13, 1)) # 15
print(toggle_bit(13, 0)) # 12
print(toggle_bit(8, 3)) # 0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
return n ^ (1 << i)
```
এটাই হৃদয়। `1 << i` বানায় mask (শুধু target-এ 1)। `n ^ mask`: target ঘরে `^ 1` → flip (0↔1), বাকি ঘরে mask-এ 0 থাকায় `^ 0` → অপরিবর্তিত। তাই ঠিক একটা ঘর উল্টোয়।
```text
return (n & (1 << i)) != 0
```
054-এর check — যাচাইয়ের জন্য।
`assert` লাইন আর nested `for` loop দুটো জিনিস যাচাই করছে: (১) একবার toggle করলে bit সত্যিই flip হয় (`is_set` উল্টে যায়), (২) দুবার toggle করলে ঠিক মূল সংখ্যা ফেরে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
15
12
0
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: (13,1)→15, (13,0)→12, (8,3)→0। সব `assert` (flip + double-toggle যাচাই loop সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(1)** — একটা shift, একটা XOR। `n`-এর আকারে কাজ বাড়ে না।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — কোনো list/array লাগছে না; কয়েকটা int মাত্র।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`^` কে power ভাবা** — Python-এ power হলো `**`, XOR হলো `^`। `5 ^ 2 = 7` (XOR), `5 ** 2 = 25` (power)। গুলিয়ো না।
2. **toggle-কে set বা clear ভাবা** — toggle জ্বলা থাকলে নেভায়, নেভানো থাকলে জ্বালায় — অবস্থার উপর নির্ভরশীল। set/clear সবসময় একই দিকে যায়।
3. **Precedence ফাঁদ** — bracket দাও: `n ^ (1 << i)`।
4. **দুবার toggle মনে না রাখা** — interview-তে কাজে লাগে: একই flip দুবার = কিছুই হলো না (`a ^ a = 0`)।
5. **`1 << i` ভুলে `i << 1` লেখা** — mask মানে "1-কে i ঘর বাঁয়ে"।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **060 — Odd One Out using XOR** (এই repo) — `a ^ a = 0` ধর্ম দিয়ে একলা সংখ্যা খোঁজা।
- **061 — Find Two Unique Numbers** (এই repo) — XOR-এর partition trick।
- **064 — Gray Code** (এই repo) — `n ^ (n >> 1)`, XOR দিয়ে সুন্দর ক্রম।
- **LeetCode — Single Number** (