057 — Toggle ith Bit¶
পাঁচ primitive-এর চতুর্থ ভাই — toggle। জ্বলা থাকলে নেভাও, নেভানো থাকলে জ্বালাও। মানে একটা switch-কে "উল্টে" দাও। হাতিয়ার আবার সেই
mask = 1 << i, কিন্তু এবার operator^(XOR)। আর এই XOR-ই হলো এই পুরো level-এর সবচেয়ে জাদুকরি operator — 060, 061, 066-এ এর আসল খেলা দেখবে। আজ তার সাথে প্রথম পরিচয়।
Source¶
- 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^)
1. Problem in simple words¶
একটা integer n আর index i দেওয়া আছে। তোমাকে n-এর i-তম bit উল্টে (flip করে) নতুন সংখ্যা ফেরত দিতে হবে।
- bit 1 হলে → 0 হয়ে যাবে
- bit 0 হলে → 1 হয়ে যাবে
যেমন n = 13 = 1101:
একই operation দুবার করলে আবার আগের জায়গায় ফিরে আসে — এটাই toggle-এর মজা।
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→ অপরিবর্তিত
মানে ঠিক একটা ঘর উল্টে যায়, বাকি কেউ নড়ে না।
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)-এ আসল তারকা হয়ে উঠবে।
4. Real-life analogy¶
সুইচবোর্ডে সেই magic switch। কিন্তু এবার তুমি জানোই না light টা এখন on না off — তুমি শুধু toggle button চাপলে। on থাকলে off হবে, off থাকলে on হবে।
আর মজাটা: একই toggle button দুবার চাপলে light আবার আগের অবস্থায় — কারণ দুটো flip একে অপরকে বাতিল করে। এই "যা আছে তার উল্টো" আর "দুবার করলে আগের জায়গায়" — দুটোই XOR-এর গভীর ধর্ম, যা পরে বড় problem-এ কাজে লাগবে।
5. Visual explanation¶
n = 13, প্রথমে i = 1 (নেভানো → জ্বলবে):
এখন i = 0 (জ্বলা → নিভবে):
দুবার toggle করলে ফিরে আসে:
6. Example input and output¶
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 = মূল সংখ্যা।
7. Brute force thinking¶
mask না জানলে, আগে bit-টা পড়ে (054) তারপর উল্টোটা বসানো মাথায় আসে — অর্থাৎ if-else দিয়ে set বা clear বেছে নেওয়া:
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 এক লাইনে দুই ক্ষেত্রই সামলায়।
brute : bit পড়ো -> if জ্বলা তো clear, নাহলে set (branch লাগে)
smart : n ^ (1 << i) (কোনো branch নেই)
XOR-এর সৌন্দর্য — সে নিজেই জানে কোনটা flip করতে হবে, আমাদের জিজ্ঞেস করতে হয় না।
9. Better thinking¶
mask দিয়ে এক ধাপে XOR করো:
কোনো 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 করে দেবে।
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 মূলে ফিরিয়ে আনল ✓।
12. Python solution¶
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¶
এটাই হৃদয়। 1 << i বানায় mask (শুধু target-এ 1)। n ^ mask: target ঘরে ^ 1 → flip (0↔1), বাকি ঘরে mask-এ 0 থাকায় ^ 0 → অপরিবর্তিত। তাই ঠিক একটা ঘর উল্টোয়।
054-এর check — যাচাইয়ের জন্য।
assert লাইন আর nested for loop দুটো জিনিস যাচাই করছে: (১) একবার toggle করলে bit সত্যিই flip হয় (is_set উল্টে যায়), (২) দুবার toggle করলে ঠিক মূল সংখ্যা ফেরে। সব ঠিক থাকলে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম তিন লাইন তিনটা print থেকে: (13,1)→15, (13,0)→12, (8,3)→0। সব assert (flip + double-toggle যাচাই loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।
15. Time complexity¶
O(1) — একটা shift, একটা XOR। n-এর আকারে কাজ বাড়ে না।
16. Space complexity¶
O(1) — কোনো list/array লাগছে না; কয়েকটা int মাত্র।
17. Common mistakes¶
^কে power ভাবা — Python-এ power হলো**, XOR হলো^।5 ^ 2 = 7(XOR),5 ** 2 = 25(power)। গুলিয়ো না।- toggle-কে set বা clear ভাবা — toggle জ্বলা থাকলে নেভায়, নেভানো থাকলে জ্বালায় — অবস্থার উপর নির্ভরশীল। set/clear সবসময় একই দিকে যায়।
- Precedence ফাঁদ — bracket দাও:
n ^ (1 << i)। - দুবার toggle মনে না রাখা — interview-তে কাজে লাগে: একই flip দুবার = কিছুই হলো না (
a ^ a = 0)। 1 << iভুলেi << 1লেখা — mask মানে "1-কে i ঘর বাঁয়ে"।
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 (https://leetcode.com/problems/single-number/) — XOR cancel-এর classic।
19. Pattern learned¶
Toggle bit with XOR — n ^ (1 << i)। বড় শিক্ষা: ^ 1 flip করে, ^ 0 অপরিবর্তিত রাখে; XOR নিজেই "উল্টো" করে, অবস্থা জানতে হয় না। আর a ^ a = 0 — দুবার toggle = মূল। এই দুই ধর্ম পরের XOR-problem গুলোর প্রাণ।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "i-তম bit উল্টাতে n ^ (1 << i); XOR নিজেই flip করে, if-else লাগে না। মনে রাখো a ^ a = 0 — দুবার toggle মূলে ফেরায়। এই XOR-ই Single Number-এর চাবি।"
পরের ধাপ → 058 — Count Set Bits (এবার n & (n - 1) দিয়ে কতগুলো bit জ্বলা গুনব)। সম্পর্কিত → 060 — Odd One Out using XOR · 054 — Check ith Bit।
ফিরে দেখা: এই 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"।