Skip to content

Problems — Level 4: Bit Manipulation

এই folder-এ Level 4-এর 14টা problem-এর note থাকবে। প্রতিটার জন্য আলাদা .md file — নিজের ভাষায় problem বোঝা, bit-এর ছবি আঁকা, dry run, code আর ভুল থেকে শেখা।

কীভাবে problem গুলো use করবে?

প্রতিটা problem-এর note লেখা হয় ../../../templates/math-problem-note-template.md follow করে — ২০টা section-এর template: problem বোঝা → brute force → optimization → dry run → complexity → "ভবিষ্যতের আমাকে এক লাইনে কী বলব"। শুরুতে template-টা একবার পড়ে নাও।

নিয়মটা আগের মতোই:

  1. Table থেকে problem নাও (recommended order ../README.md-তে)
  2. খাতায় binary লিখে নিজে চেষ্টা করো অন্তত 20-30 মিনিট — bit problem-এ ছোট সংখ্যায় (4-bit) হাতে চালানোই আসল চাবি
  3. তারপর note file বানাও/পড়ো, নিজের approach মেলাও
  4. Solve হলে Status planned → done

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
053 Binary Representation Easy base conversion — Classic exercise 053-binary-representation.md planned
054 Check ith Bit Easy mask & 053 Classic exercise 054-check-ith-bit.md planned
055 Set ith Bit Easy mask OR 054 Classic exercise 055-set-ith-bit.md planned
056 Clear ith Bit Easy mask & ~ 054 Classic exercise 056-clear-ith-bit.md planned
057 Toggle ith Bit Easy mask ^ 054 Classic exercise 057-toggle-ith-bit.md planned
058 Count Set Bits Easy n&(n-1) loop 054 LeetCode Number of 1 Bits — https://leetcode.com/problems/number-of-1-bits/ (related: Counting Bits — https://leetcode.com/problems/counting-bits/) 058-count-set-bits.md planned
059 Power of Two Easy n&(n-1)==0 058 LeetCode — https://leetcode.com/problems/power-of-two/ 059-power-of-two.md planned
060 Odd One Out using XOR Easy XOR cancel 053 LeetCode Single Number — https://leetcode.com/problems/single-number/ 060-odd-one-out-xor.md planned
061 Find Two Unique Numbers Medium XOR partition 060 LeetCode Single Number III — https://leetcode.com/problems/single-number-iii/ 061-find-two-unique-numbers.md planned
062 Subset Generation using Bits Medium bitmask enumeration 047, 054 LeetCode Subsets — https://leetcode.com/problems/subsets/ 062-subset-generation-bits.md planned
063 Bitmask DP Intro Hard state as mask 062 USACO Guide — https://usaco.guide/gold/dp-bitmasks 063-bitmask-dp-intro.md planned
064 Gray Code Medium n^(n>>1) 053 LeetCode — https://leetcode.com/problems/gray-code/ 064-gray-code.md planned
065 AND/OR/XOR Range Tricks Medium common prefix 054 LeetCode Bitwise AND of Numbers Range — https://leetcode.com/problems/bitwise-and-of-numbers-range/ 065-and-or-xor-range-tricks.md planned
066 Maximum XOR Pair Hard greedy by bit / trie 060 LeetCode — https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/ 066-maximum-xor-pair.md planned

"Inherits from" column-টা কী?

প্রতিটা problem আগের কারো কাঁধে দাঁড়িয়ে। 053 (binary পড়া) হলো বর্ণমালা; 054 (check) থেকে set/clear/toggle তিন ভাই; 058-এর n & (n - 1) থেকেই 059-এর power check। আটকে গেলে আগে "Inherits from" problem-টায় ফিরে যাও।

053 (binary পড়া) ──> 054 (check) ──> 055 (set)
   │                    ├──────────> 056 (clear)
   │                    ├──────────> 057 (toggle)
   │                    ├──> 058 (popcount) ──> 059 (power of 2)
   │                    ├──> 062 (subsets) ──> 063 (bitmask DP)
   │                    └──> 065 (range AND)
   ├──> 060 (XOR একলা) ──> 061 (একলা দুজন)
   │         └──────────> 066 (max XOR pair)
   └──> 064 (gray code)

একটা ছোট পরামর্শ

Bit problem-এ সবচেয়ে বড় ফাঁদ হলো decimal-এ ভাবা। প্রতিটা problem-এ অন্তত একবার সংখ্যাগুলোর binary form খাতায় লিখো — 4-bit-এই যথেষ্ট। যে trick ছোট সংখ্যায় চোখে দেখেছ, বড় সংখ্যায় সেটা এমনিই বিশ্বাস হবে। আর & vs and, precedence-এর bracket — এই ভুলগুলোর তালিকা ../README.md-র Common mistakes section-এ আছে, প্রতি problem-এর আগে একবার চোখ বুলাও।

Concept ঝালাই করতে → ../concept-notes.md। ছবি এঁকে বুঝতে → ../visualization-ideas.md।