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"। চলো।

Problem link ও উৎস

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-এর আচরণ)

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

দুটো সংখ্যা 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।

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

চেনা উদাহরণে বোঝা¶

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

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

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

দাঁড়িয়ে আছে 054 (Check ith Bit) আর binary বোঝার (053) উপর। এখানে নতুনত্ব — একটা bit একটা সংখ্যায় নয়, পুরো range জুড়ে কেমন আচরণ করে সেটা ভাবা। নিচের bit গুলো range-এ "টগল" করে, উপরের bit গুলো স্থির — এই দৃষ্টিটাই চাবি।

এটা bit-প্যাটার্নের একটা স্বতন্ত্র প্রয়োগ; concept হিসেবে segment tree-র range query বা prefix-এর চিন্তার সাথে দূরসম্পর্ক আছে, কিন্তু এখানে আমরা শুধু "range AND = common prefix" intuition-এ মন দেব।

ভেতরের অঙ্ক¶

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

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

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 বিশাল হলে?

কোথায় বেশি কাজ হতে পারে¶

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-সংখ্যার সমান।

আরও ভালোভাবে ভাবা¶

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 বের করেই উত্তর।

ভাবনার পরিবর্তন¶

আসল "আহা!" — 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 বের করা।

ছবিতে বোঝা¶

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 ✓

ছোট input-এ ধাপে ধাপে¶

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 ✓

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

উদাহরণ

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

Output মিলিয়ে দেখা¶

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

উদাহরণ

4
12
7
সব test pass!

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

খরচ ও সাধারণ ভুল¶

সময়¶

O(log r) — loop ঘোরে যতগুলো bit l আর r-এর আলাদা, বড়জোর সংখ্যার মোট bit-সংখ্যা। range-এর আকারের (r - l) সাথে কোনো সম্পর্ক নেই — তাই বিশাল range-ও চটজলদি।

অতিরিক্ত জায়গা¶

O(1) — শুধু shift, l, r variable; কোনো list/array নেই।

যে ভুলগুলো এড়াতে হবে¶

brute force দিয়ে বড় range করা — r - l বিশাল হলে TLE; common-prefix method লাগে।
shift ফিরিয়ে দিতে ভুলে যাওয়া — l == r-এ থামার পর l << shift করতে হবে; নাহলে উত্তর অনেক ছোট হবে।
>>= ভুলে >> লেখা — l >> 1 শুধু মান দেয়, l-কে বদলায় না; চাই l >>= 1।
l == r edge case — loop একবারও চলবে না, shift = 0, উত্তর l — এটাই ঠিক (একটাই সংখ্যা)।
AND আর OR/XOR গুলিয়ে ফেলা — এই trick range AND-এর জন্য; OR/XOR-এর pattern আলাদা (XOR-এ prefix-XOR trick: xor(0..r) ^ xor(0..l-1))।

শেখা ও পরের অনুশীলন¶

এই ধারণার পরের অনুশীলন¶

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

কৌশলটি মনে রাখুন¶

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

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে এক লাইনে: "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"।