055 — Set ith Bit¶

054-এ শিখলে একটা bit "পড়তে" (check)। আজ শিখব সেটা জ্বালাতে (set)। একই টর্চলাইট mask = 1 << i, কিন্তু এবার &-এর বদলে | (OR)। পাঁচটা primitive-এর দ্বিতীয় ভাই — আর তুমি দেখবে কত মিল আগেরটার সাথে। ছোট সংখ্যায় খাতায় মিলিয়ে নিও।

Source¶

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 বদল)

1. Problem in simple words¶

একটা integer n আর index i দেওয়া আছে। তোমাকে n-এর i-তম bit-টা জ্বালিয়ে (1 বানিয়ে) নতুন সংখ্যাটা ফেরত দিতে হবে।

bit আগে থেকেই 1 হলে → কিছু বদলাবে না
bit 0 হলে → সেটা 1 হয়ে যাবে, সংখ্যা বাড়বে

যেমন n = 13 = 1101, i = 1:

1101  ->  ঘর 1 জ্বালাও  ->  1111 = 15

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 → অপরিবর্তিত

মানে শুধু একটা ঘর জ্বলে, বাকি কেউ টের পায় না।

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-এর স্বভাব মনে রাখো।

4. Real-life analogy¶

সেই সুইচবোর্ডে ফিরি। তোমার হাতে এমন একটা magic switch (mask) যেটা শুধু i নম্বর light-এ লাগানো। তুমি সেটা জোর করে on করে দিলে।

light আগে on ছিল? on-ই থাকল, কিছু বদলালো না।
light off ছিল? এবার জ্বলে উঠল।

বাকি কোনো light-এ তোমার হাত পড়েনি — তারা যেমন ছিল তেমনই। এই "জোর করে on" করাই | mask।

5. Visual explanation¶

n = 13, i = 1 — set:

n       = 1 1 0 1     (13)
mask    = 0 0 1 0     (1 << 1)
        --- --- --- ---
n | mask= 1 1 1 1     (15)   ঘর 1 জ্বলে উঠল, বাকি অক্ষত ✓

এখন এমন ঘর যেটা আগেই জ্বলা (i = 0) — কিছু বদলায় না:

n       = 1 1 0 1
mask    = 0 0 0 1     (1 << 0)
        --- --- --- ---
n | mask= 1 1 0 1     (13)   ঘর 0 আগেই 1 ছিল -> অপরিবর্তিত

লক্ষ করো — | কখনো কোনো bit নেভায় না, শুধু জ্বালাতে পারে (বা একই রাখে)।

6. Example input and output¶

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"।

7. Brute force thinking¶

mask না জানলে, প্রথমে binary list বানিয়ে (053-এর মতো) ওই index-এ জোর করে 1 বসিয়ে আবার সংখ্যায় ফেরা মাথায় আসে:

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।

brute : list ভাঙো -> index-এ 1 বসাও -> আবার সংখ্যা গড়ো  (O(log n))
smart : n | (1 << i)                                    (O(1))

এক bit জ্বালানোর জন্য পুরো সংখ্যা ভাঙা-গড়া — খাঁটি অপচয়।

9. Better thinking¶

mask দিয়ে এক ধাপে OR করো:

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-এর স্বভাব আলাদা — এটাই পুরো খেলা।

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।

12. Python solution¶

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¶

return n | (1 << i)

এটাই হৃদয়। 1 << i বানায় mask — শুধু i-তম ঘরে 1। n | mask: target ঘরে জোর করে 1 (set), আর বাকি ঘরে mask-এ 0 থাকায় bit | 0 = bit → অপরিবর্তিত। তাই ঠিক একটা ঘর জ্বলে।

return (n & (1 << i)) != 0

এটা 054-এর check — শুধু যাচাইয়ের জন্য রাখা, যাতে test-এ "set করার পর সত্যিই জ্বলা" নিশ্চিত করা যায়।

assert লাইনগুলো আর nested for loop নিজেরা যাচাই করছে: set করার পর bit সবসময় জ্বলা, আর সংখ্যা হয় অপরিবর্তিত (আগেই জ্বলা থাকলে) নয়তো ঠিক 1 << i বাড়ে। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough¶

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

15
13
8
সব test pass!

প্রথম তিন লাইন তিনটা print থেকে: (13,1)→15, (13,0)→13 (অপরিবর্তিত), (0,3)→8। সব assert (যাচাই loop সহ) চুপচাপ pass করেছে। শেষে সব test pass!।

15. Time complexity¶

O(1) — একটা shift, একটা OR। n-এর আকারে কাজ বাড়ে না; পুরো সংখ্যা না ভেঙে শুধু একটা ঘর জ্বালাচ্ছি।

16. Space complexity¶

O(1) — কোনো list বা array লাগছে না; কয়েকটা int মাত্র।

17. Common mistakes¶

| আর or গুলিয়ে ফেলা — bitwise কাজে সবসময় |, logical or নয়।
1 << i ভুলে i << 1 লেখা — 1 << 3 = 8 (mask), 3 << 1 = 6 (double)।
set আর toggle গুলিয়ে ফেলা — set (|) আগেই জ্বলা bit-কে জ্বালাই রাখে; toggle (^) সেটাকে নিভিয়ে দিত! দুটো আলাদা।
Precedence ফাঁদ — অন্য expression-এর সাথে মেশালে bracket দাও: (n | (1 << i))।
Negative i বা বিশাল i — 1 << -1 ValueError; খুব বড় i memory খাবে।

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 (https://leetcode.com/problems/single-number/) — bit-by-bit চিন্তার পরের ধাপ।
LeetCode — Subsets (https://leetcode.com/problems/subsets/) — mask দিয়ে subset বানানোয় set-idea কাজে লাগে।

19. Pattern learned¶

Set bit with OR — n | (1 << i)। বড় শিক্ষা: | শুধু জ্বালায় (force-1), কখনো নেভায় না; mask-এর 0-গুলো বাকি সব ঘর অক্ষত রাখে। check/set/clear/toggle — সবার মূলে এক mask, শুধু operator-এর স্বভাব আলাদা।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "i-তম bit জ্বালাতে n | (1 << i); OR জোর করে 1 বানায়, বাকি ঘর mask-এর 0-তে অক্ষত। set vs toggle গুলিয়ো না।"

পরের ধাপ → 056 — Clear ith Bit (এবার একই mask উল্টে bit নেভাব)। সম্পর্কিত → 054 — Check ith Bit · 057 — Toggle 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"।