065 — AND/OR/XOR Range Tricks

পরপর অনেকগুলো সংখ্যার AND (বা OR, XOR) — 5 AND 6 AND 7 AND ... AND r। naive ভাবে loop চালিয়ে করতে পারো, কিন্তু range বিশাল হলে (যেমন l=0, r=10^9) সেটা অসম্ভব ধীর। এখানে একটা সুন্দর pattern আছে — range AND আসলে l আর r-এর common binary prefix। এই একটা intuition ধরতে পারলে loop ছাড়াই O(log r)-এ উত্তর। Medium, interview-তে "Bitwise AND of Numbers Range"। চলো।

Source

• Original source: LeetCode — Bitwise AND of Numbers Range
• Platform: LeetCode — https://leetcode.com/problems/bitwise-and-of-numbers-range/
• 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-এর আচরণ)

1. Problem in simple words

দুটো সংখ্যা l আর r দেওয়া আছে (l ≤ r)। তোমাকে বের করতে হবে l থেকে r পর্যন্ত সব সংখ্যার bitwise AND:

l AND (l+1) AND (l+2) AND ... AND r

যেমন l = 5, r = 7:

5 AND 6 AND 7 = ?
5 = 101, 6 = 110, 7 = 111

উত্তর হবে শুধু সেই bit-গুলো যেগুলো 5, 6, 7 — সবার মধ্যেই 1।

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-এ পৌঁছাও), কয় ঘর সরালে গুনে রাখো, শেষে আবার বাঁয়ে ফিরিয়ে দাও।

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-এ মন দেব।

4. Real-life analogy

ভাবো একদল মানুষের ঠিকানা — সবাই একই এলাকায় থাকে। l থেকে r পর্যন্ত বাড়ির নম্বর। তুমি জিজ্ঞেস করছ — "সবার ঠিকানায় কোন অংশটা একই?"

বড় অংশ (দেশ, শহর, এলাকা — উপরের bit) সবার এক। কিন্তু বাড়ির ছোট নম্বর (নিচের bit) প্রতিটা মানুষে আলাদা — পরপর নম্বর তো বদলায়ই। তাই "সবার যেটা একই" = উপরের common অংশ (prefix), নিচের আলাদা অংশটা বাদ। range AND ঠিক সেই common উপরের অংশটাই রাখে, নিচের বদলে-যাওয়া অংশ মুছে দেয়।

5. Visual explanation

l = 5, r = 7 — নিচের bit range-এ বদলায়, তাই AND-এ 0:

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):

শুরু  : 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 ✓

6. Example input and output

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 হয়ে যায়।

7. Brute force thinking

pattern না জানলে, সরাসরি loop চালিয়ে AND করা স্বাভাবিক:

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।

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 করো যতক্ষণ সমান না হয়, তারপর আবার বাঁয়ে ফিরিয়ে দাও:

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 বের করা।

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:

1100, 1111 -> shift -> 110, 111 -> shift -> 11, 11 সমান, shift=2
ফল: 11 << 2 = 1100 = 12 ✓

12. Python solution

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

while l < r:
    l >>= 1
    r >>= 1
    shift += 1

এটাই হৃদয়। যতক্ষণ l আর r আলাদা, দুটোকেই এক ঘর ডানে সরাই (নিচের আলাদা bit ফেলে দিই) আর কয় ঘর সরালাম গুনি। l == r হলে আমরা common prefix-এ পৌঁছেছি (নিচের সব আলাদা bit ফেলা হয়ে গেছে)।

return l << shift

এখন l (= r) হলো common prefix; সেটাকে আবার shift ঘর বাঁয়ে সরাই — নিচের ঘরগুলো 0 দিয়ে ভরে। এটাই range AND।

result &= x

brute version: l থেকে r পর্যন্ত প্রতিটা সংখ্যা একে একে AND — যাচাইয়ের জন্য।

assert লাইন আর nested for loop দুই method-কে 0 থেকে 39 সব range-এ মিলিয়ে নিচ্ছে, আর বড় range-এ formula-র দ্রুততা দেখাচ্ছে। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

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

4
12
7
সব test pass!

প্রথম তিন লাইন তিনটা print থেকে: (5,7)→4, (12,15)→12, (7,7)→7। সব assert (cross-check loop আর বড়-range যাচাই সহ) চুপচাপ pass করেছে। শেষে সব test pass!।

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

18. Harder problems that inherit this idea

• LeetCode — Bitwise AND of Numbers Range (https://leetcode.com/problems/bitwise-and-of-numbers-range/) — এই problem-এরই মূল রূপ।
• LeetCode — XOR Queries of a Subarray (https://leetcode.com/problems/xor-queries-of-a-subarray/) — prefix-XOR দিয়ে range XOR।
• LeetCode — XOR Operation in an Array (https://leetcode.com/problems/xor-operation-in-an-array/) — range জুড়ে XOR প্যাটার্ন।
• Codeforces — XOR/AND range constructive (https://codeforces.com/problemset) — range bit-pattern চিন্তা CP-তে বারবার।

19. Pattern learned

Range AND = common prefix — l আর r-কে একসাথে ডানে shift করে common prefix বের করা, তারপর ফিরিয়ে দেওয়া। বড় শিক্ষা: range AND-এ একটা bit টিকতে সবার মধ্যে 1 লাগে; নিচের bit range-এ বদলে গিয়ে 0 হয়, তাই শুধু l, r-এর common উপরের অংশ টেকে — পুরো range ছুঁতে হয় না।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "range AND = l, r-এর common binary prefix। দুটোকে একসাথে >> 1 করো যতক্ষণ সমান না হয়, তারপর << shift। বিশাল range-এও O(log r); brute force-এর loop লাগে না। range-এ পরপর AND দেখলেই common prefix মনে করব।"

পরের ধাপ → 066 — Maximum XOR Pair (এ level-এর শেষ — greedy by bit, trie-র দরজায় টোকা)। সম্পর্কিত → 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"।