Problem link ও উৎস
- **Original source:** LeetCode — Bitwise AND of Numbers Range
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 4: Bit Manipulation → range AND, common prefix
- **Difficulty:** Medium
- **Pattern:** common prefix (range AND = l আর r-এর common binary prefix)
- **Basic idea inherited from:** 054 — Check ith Bit (bit বোঝা; এখানে range জুড়ে bit-এর আচরণ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো সংখ্যা `l` আর `r` দেওয়া আছে (`l ≤ r`)। তোমাকে বের করতে হবে `l` থেকে `r` পর্যন্ত **সব** সংখ্যার bitwise AND:
```text
l AND (l+1) AND (l+2) AND ... AND r
```
যেমন `l = 5, r = 7`:
```text
5 AND 6 AND 7 = ?
5 = 101, 6 = 110, 7 = 111
```
উত্তর হবে শুধু সেই bit-গুলো যেগুলো 5, 6, 7 — সবার মধ্যেই 1।
### Input ও output {#6-example-input-and-output}
```text
l, r -> output
-------------------
5, 7 -> 4 (101 & 110 & 111 = 100)
0, 0 -> 0 (একটাই সংখ্যা: 0)
7, 7 -> 7 (l == r, সংখ্যাটাই উত্তর)
1, 2 -> 0 (01 & 10 = 00)
6, 7 -> 6 (110 & 111 = 110)
0, 1 -> 0 (00 & 01 = 00)
12, 15 -> 12 (1100 & 1101 & 1110 & 1111 = 1100)
```
edge case: `l == r` → range-এ একটাই সংখ্যা, তাই সেটাই AND (যেমন 7,7 → 7)। আর range-এ 0 থাকলে (0,1) সাধারণত AND 0 হয়ে যায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একদল মানুষের ঠিকানা — সবাই একই এলাকায় থাকে। `l` থেকে `r` পর্যন্ত বাড়ির নম্বর। তুমি জিজ্ঞেস করছ — "সবার ঠিকানায় কোন অংশটা **একই**?"
বড় অংশ (দেশ, শহর, এলাকা — উপরের bit) সবার এক। কিন্তু বাড়ির ছোট নম্বর (নিচের bit) প্রতিটা মানুষে আলাদা — পরপর নম্বর তো বদলায়ই। তাই "সবার যেটা একই" = উপরের common অংশ (prefix), নিচের আলাদা অংশটা বাদ। range AND ঠিক সেই common উপরের অংশটাই রাখে, নিচের বদলে-যাওয়া অংশ মুছে দেয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দাঁড়িয়ে আছে **054 (Check ith Bit)** আর binary বোঝার (053) উপর। এখানে নতুনত্ব — একটা bit একটা সংখ্যায় নয়, পুরো **range জুড়ে** কেমন আচরণ করে সেটা ভাবা। নিচের bit গুলো range-এ "টগল" করে, উপরের bit গুলো স্থির — এই দৃষ্টিটাই চাবি।
এটা bit-প্যাটার্নের একটা স্বতন্ত্র প্রয়োগ; concept হিসেবে segment tree-র range query বা prefix-এর চিন্তার সাথে দূরসম্পর্ক আছে, কিন্তু এখানে আমরা শুধু "range AND = common prefix" intuition-এ মন দেব।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল observation: **range AND = `l` আর `r`-এর common binary prefix** (উপরের যে অংশটুকু দুজনের মেলে), বাকি নিচের সব bit 0।
কেন? AND-এ একটা bit 1 থাকতে হলে range-এর **প্রতিটা** সংখ্যায় সেই bit 1 হতে হবে। কিন্তু পরপর সংখ্যায় নিচের bit-গুলো এত ঘনঘন 0↔1 বদলায় যে range-এর ভেতরে কোথাও না কোথাও সেই bit 0 পড়েই যায় — তাই নিচের bit গুলো AND-এ 0 হয়ে যায়। টিকে থাকে শুধু উপরের যে bit-গুলো `l` থেকে `r` পর্যন্ত অপরিবর্তিত, মানে common prefix।
Algorithm: `l` আর `r` দুটোকেই ডানে shift করতে থাকো যতক্ষণ না সমান হয় (common prefix-এ পৌঁছাও), কয় ঘর সরালে গুনে রাখো, শেষে আবার বাঁয়ে ফিরিয়ে দাও।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
pattern না জানলে, সরাসরি loop চালিয়ে AND করা স্বাভাবিক:
```python
def range_and_brute(l, r):
result = l
for x in range(l + 1, r + 1):
result &= x
return result
```
কাজ করে — `l` থেকে `r` পর্যন্ত প্রতিটা সংখ্যা AND করি। ছোট range-এ একদম ঠিক। কিন্তু range বিশাল হলে?
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
brute force loop ঘোরে `(r - l)` বার। `l = 0, r = 10^9` হলে loop প্রায় 100 কোটি বার চলবে — interview-তে Time Limit Exceeded।
```text
l = 0, r = 2147483647 (প্রায় 2^31):
brute : ~2 বিলিয়ন বার AND (অসম্ভব ধীর)
common prefix: ~31 বার shift (O(log r), চোখের নিমেষে)
```
মূল কথা: range-এর প্রতিটা সংখ্যা ছুঁতে হয় না — উত্তর তো শুধু l আর r-এর উপর নির্ভরশীল (common prefix)। তাই range যত বড়ই হোক, কাজ লাগে শুধু bit-সংখ্যার সমান।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
`l` আর `r`-কে একসাথে ডানে shift করো যতক্ষণ সমান না হয়, তারপর আবার বাঁয়ে ফিরিয়ে দাও:
```python
def range_and(l, r):
shift = 0
while l < r:
l >>= 1
r >>= 1
shift += 1
return l << shift # common prefix, নিচে shift টা 0
```
loop ঘোরে শুধু `O(log r)` বার (যতগুলো bit আলাদা)। range-এর আকারের সাথে কোনো সম্পর্ক নেই — l আর r-এর common prefix বের করেই উত্তর।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **range AND-এ একটা bit টিকতে হলে range-এর সবার মধ্যে সেটা 1 হতে হবে; কিন্তু পরপর সংখ্যায় নিচের bit এত বদলায় যে তারা কোথাও না কোথাও 0 পড়ে — তাই টিকে থাকে শুধু l আর r-এর common উপরের অংশ (prefix)।**
naive চিন্তায় আমরা প্রতিটা সংখ্যা ধরে AND করি। কিন্তু insight: উত্তর শুধু l আর r-এর উপর নির্ভর করে, মাঝের সংখ্যাগুলোর উপর নয়। নিচের যে bit-গুলোয় l আর r আলাদা — সেখানে range পার হওয়ার সময় অবশ্যই carry হয়, মানে সেই bit একবার 0 হয়, তাই AND-এ মুছে যায়। উপরের যে অংশ l থেকে r পর্যন্ত স্থির, সেটাই টেকে। তাই "দুজনকে একসাথে ডানে shift করে কখন মিলছে দেখা" = common prefix বের করা।
### ছবিতে বোঝা {#5-visual-explanation}
`l = 5, r = 7` — নিচের bit range-এ বদলায়, তাই AND-এ 0:
```text
5 = 1 0 1
6 = 1 1 0
7 = 1 1 1
AND 1 0 0 = 4 <- শুধু সবার মধ্যে যে bit 1, সেটা টেকে
```
লক্ষ করো — সবচেয়ে উপরের bit (মান 4) তিনটাতেই 1, তাই টিকল। নিচের bit গুলো কোথাও না কোথাও 0, তাই গেল।
Shift-method চলার ছবি (`l = 5, r = 7`):
```text
শুরু : l = 101, r = 111 সমান নয়, shift -> l=10, r=11, count=1
ধাপ 2 : l = 10, r = 11 সমান নয়, shift -> l=1, r=1, count=2
ধাপ 3 : l = 1, r = 1 সমান! থামো
ফলাফল : common prefix = 1, আবার count=2 ঘর বাঁয়ে -> 1 << 2 = 100 = 4 ✓
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`l = 5, r = 7`:
| step | l (binary) | r (binary) | l < r? | কাজ | shift |
| --- | --- | --- | --- | --- | --- |
| 1 | 101 | 111 | হ্যাঁ | দুটোই >> 1 | 1 |
| 2 | 10 | 11 | হ্যাঁ | দুটোই >> 1 | 2 |
| 3 | 1 | 1 | না | থামো | 2 |
এখন `l = 1`, `shift = 2` → `l << shift = 1 << 2 = 4`। উত্তর `4` ✓। মিলিয়ে দেখো `5 & 6 & 7 = 4`।
আরেকটা, `l = 12, r = 15`:
```text
1100, 1111 -> shift -> 110, 111 -> shift -> 11, 11 সমান, shift=2
ফল: 11 << 2 = 1100 = 12 ✓
```
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def range_and(l, r):
"""l থেকে r পর্যন্ত সব সংখ্যার bitwise AND = l, r-এর common prefix।"""
shift = 0
while l < r:
l >>= 1
r >>= 1
shift += 1
return l << shift
def range_and_brute(l, r):
"""একই উত্তর সরাসরি loop দিয়ে (যাচাইয়ের জন্য)।"""
result = l
for x in range(l + 1, r + 1):
result &= x
return result
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert range_and(5, 7) == 4 # 101 & 110 & 111 = 100
assert range_and(0, 0) == 0 # একটাই সংখ্যা
assert range_and(7, 7) == 7 # l == r
assert range_and(1, 2) == 0 # 01 & 10 = 00
assert range_and(6, 7) == 6 # 110 & 111 = 110
assert range_and(0, 1) == 0
assert range_and(12, 15) == 12 # 1100..1111 -> 1100
# common-prefix method আর brute force একই উত্তর দেয় (ছোট range-এ)
for l in range(0, 40):
for r in range(l, 40):
assert range_and(l, r) == range_and_brute(l, r)
# বড় range-এ brute অসম্ভব, কিন্তু formula চোখের নিমেষে:
assert range_and(0, 2147483647) == 0
assert range_and(1000000, 1000000) == 1000000
print(range_and(5, 7)) # 4
print(range_and(12, 15)) # 12
print(range_and(7, 7)) # 7
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
while l < r:
l >>= 1
r >>= 1
shift += 1
```
এটাই হৃদয়। যতক্ষণ `l` আর `r` আলাদা, দুটোকেই এক ঘর ডানে সরাই (নিচের আলাদা bit ফেলে দিই) আর কয় ঘর সরালাম গুনি। `l == r` হলে আমরা common prefix-এ পৌঁছেছি (নিচের সব আলাদা bit ফেলা হয়ে গেছে)।
```text
return l << shift
```
এখন `l` (= `r`) হলো common prefix; সেটাকে আবার `shift` ঘর বাঁয়ে সরাই — নিচের ঘরগুলো 0 দিয়ে ভরে। এটাই range AND।
```text
result &= x
```
brute version: `l` থেকে `r` পর্যন্ত প্রতিটা সংখ্যা একে একে AND — যাচাইয়ের জন্য।
`assert` লাইন আর nested `for` loop দুই method-কে 0 থেকে 39 সব range-এ মিলিয়ে নিচ্ছে, আর বড় range-এ formula-র দ্রুততা দেখাচ্ছে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
4
12
7
সব test pass!
```
প্রথম তিন লাইন তিনটা `print` থেকে: (5,7)→4, (12,15)→12, (7,7)→7। সব `assert` (cross-check loop আর বড়-range যাচাই সহ) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log r)** — loop ঘোরে যতগুলো bit `l` আর `r`-এর আলাদা, বড়জোর সংখ্যার মোট bit-সংখ্যা। range-এর আকারের (`r - l`) সাথে কোনো সম্পর্ক নেই — তাই বিশাল range-ও চটজলদি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `shift`, `l`, `r` variable; কোনো list/array নেই।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **brute force দিয়ে বড় range করা** — `r - l` বিশাল হলে TLE; common-prefix method লাগে।
2. **shift ফিরিয়ে দিতে ভুলে যাওয়া** — `l == r`-এ থামার পর `l << shift` করতে হবে; নাহলে উত্তর অনেক ছোট হবে।
3. **`>>=` ভুলে `>>` লেখা** — `l >> 1` শুধু মান দেয়, `l`-কে বদলায় না; চাই `l >>= 1`।
4. **`l == r` edge case** — loop একবারও চলবে না, `shift = 0`, উত্তর `l` — এটাই ঠিক (একটাই সংখ্যা)।
5. **AND আর OR/XOR গুলিয়ে ফেলা** — এই trick range **AND**-এর জন্য; OR/XOR-এর pattern আলাদা (XOR-এ prefix-XOR trick: `xor(0..r) ^ xor(0..l-1)`)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Bitwise AND of Numbers Range** (