Imagine you're planning a group outing. AND is the strict friend — "Everyone must agree, or we don't do it." Every new person added can onlyremove options. OR is the easy-going friend — "If ANYONE wants to do it, it's on the table." Every new person adds more possibilities.
This is EXACTLY how AND and OR behave across ranges:
AND is monotonically decreasing — as you AND more numbers, the result can only lose bits (1s become 0s). It can never gain a 1.
OR is monotonically increasing — as you OR more numbers, the result can only gain bits (0s become 1s). It can never lose a 1.
This asymmetry is the ENGINE behind every algorithm in this article:
Property
AND (&)
OR (|)
Direction
Only shrinks (loses bits)
Only expands (gains bits)
Range behavior
Common prefix survives, rest → 0
Bits propagate rightward
Identity
x & all-ones = x
x | 0 = x
Annihilator
x & 0 = 0
x | all-ones = all-ones
Idempotent
x & x = x
x | x = x
Key Insight
🔑 The Key Insight: AND can only clear bits as you extend a range. OR can only set bits. This monotonicity is what lets us compute range AND in O(log n) instead of O(n), and why OR-of-subarrays problems have bounded complexity of O(32n).
Problem 1
1. Range Bitwise AND — The Common Prefix Trick
Problem: Given two integers left and right, compute the bitwise AND of ALL numbers in the inclusive range [left, right].
If the range is [5, 7], we need: 5 & 6 & 7.
Note
🏗️ Real-World Analogy: Imagine you're looking at two buildings — the leftmost and rightmost in a row. Every building between them is shorter or equal in height. The AND of a range is like finding the "common skyline" — the bits that stay 1 across ALL numbers in the range. If a bit flips to 0 anywhere in between, it stays 0. It's like asking: which columns on this skyline are uninterrupted by clouds across the entire street? The answer is the common prefix of the two end buildings — everything after the first differing column is blocked!
🤔 Let's Think About It
The naive approach: loop through every number from 5 to 7 billion? That's impossible for large ranges. There MUST be a pattern.
📋 Edge Cases to Consider
left === right: Range has one number. Return that number. The while loop doesn't execute.
left = 0: 0 AND anything = 0. Returns 0 immediately. No iterations needed.
Large range [1, 2^31-1]: The shift loop runs at most 31 iterations (one per bit). Always O(log n).
left and right differ in MSB: Only the MSB might survive. E.g., [4, 5] = 100 & 101 = 100 = 4. Common prefix is just the MSB.
left and right are consecutive powers of two: E.g., [8, 9] = 1000 & 1001 = 1000 = 8. Only the MSB survives because bit 0 changed.
Brute Force (Don't Do This)
✅ This works for tiny ranges. But for left=0, right=2³¹-1, this loops 2 billion times. We need the O(log n) trick.
✨ The Common Prefix Insight
Here's the MAGIC: The AND of a range equals the common prefix ofleft and right in binary.Everything after the first differing bit is zero.
Why? Because any bit that CHANGES within the range must go through BOTH 0 and 1. When a bit flips, its AND becomes 0. Only bits that stay CONSTANT across the entire range survive — and those constant bits are exactly the common prefix of left and right!
🔍 Real-Time Thinking — What Do I Know?
"I need AND of ALL numbers from left to right. That could be billions of numbers — no way I iterate. What happens to bits as numbers increase? Any bit that changes from 0 to 1 (or 1 to 0) within the range will have its AND become 0, because somewhere in the range that bit is both 0 and 1. Only bits that stay CONSTANT across the whole range survive. Which bits stay constant? Those in the COMMON PREFIX of left and right! Once a bit differs between left and right, it flips somewhere in between. So I just shift both left and right until they're equal, then shift back. The number of shifts = bits that changed = bits that get set to 0."
The Shift-Until-Equal Algorithm
The simplest implementation: shift both numbers right until they are equal (the diverging bits fall off), then shift the result back.
📊 Dry Run Table — Watch It In Action
Step
left
right
left < right?
Action
Start
5 (101)
7 (111)
✅
Shift both right
1
2 (010)
3 (011)
✅
Shift both right
2
1 (001)
1 (001)
❌
🔥 Equal! shift=2
Result
left << shift = 1 << 2 = 4 (100₂)
Brian Kernighan's Trick — Even Cleaner
Another approach uses n & (n-1) to clear the rightmost set bit of right until it drops below left:
Tip
⚡ Interview Tip: When you hear "bitwise AND of a range" in an interview, IMMEDIATELY say "common prefix." Explain that bits that change within the range must toggle between 0 and 1, so their AND becomes 0. Only the common prefix survives. This shows the interviewer you understand the DEEP property, not just the algorithm.
Edge Cases
left === right: Return left (or right). The range has one number.
left = 0: The result will be 0 for any right > 0 (since 0 AND anything = 0).
Large range like [1, 2³¹-1]: Shift approach takes at most 31 iterations — O(log n)!
ProblemEmbed: bitwise-and-of-numbers-range
Problem 2
2. Largest AND Combination — Counting Set Bits
Problem: Given an array of integers, find the size of the largest combination (subset) with a bitwise AND greater than zero.
🤔 The Decision: Include or Exclude?
This isn't a typical DP problem where I choose to include or exclude each element. Instead, I'm asking: "If I claim bit position k, which subset of elements must I include?" Every element with bit k set is automatically included. Elements without bit k are automatically excluded. So the decision isn't about elements — it's about bits! For each bit position, the size of the largest subset that HAS that bit set in its AND is simply the count of elements with that bit set. The answer is the maximum across all 32 bit positions.
🤔 What Does "AND > 0" Actually Mean?
For the AND of a group of numbers to be > 0, there must be at least one bit positionwhere every single number in the group has a 1. Think of it like a club: everyone must share at least one common interest.
Brute Force — Subset Enumeration
Check every subset? There are 2n subsets. For n=10⁵, that's more than the number of atoms in the universe. ❌
✨ The Bit Counting Solution
Here's the INSANELY simple trick: Count how many numbers have each bit set. The answer is the maximum count across all bit positions. That's it. No subset enumeration. No backtracking. Just counting.
Why This Works
If we pick ALL elements that have bit k set, their AND is guaranteed to have bit k set — so the AND is at least2k > 0. Could there be a larger subset that doesn't correspond to a single bit? No! If the AND > 0, at least one bit must be common to all elements. The maximum such subset is bounded by the count at that bit.
Note
💡 Think of it differently: This is an OR problem in disguise. We're asking "which numbers share a common bit?" — that's OR-like thinking (union of a property). The AND > 0 constraint just means the common bit exists.
3. Longest Nice Subarray — Sliding Window with AND
Problem: Given an array of integers, find the longest contiguous subarray where the bitwise AND of every pair of elements is zero.
Note
🅿️ Real-World Analogy: Imagine a parking lot where each parking spot (bit position) can hold at most ONE car at a time. Numbers are like cars with specific parking needs — a number parks in all the spots its 1-bits represent. A "nice" subarray means no two cars are fighting for the same parking spot. When a new car arrives, if it needs a spot that's already taken, cars leave from the front of the queue until the spot is free!
🤔 What Does "Every Pair AND = 0" Mean?
This means no two elements in the subarray can share a common set bit. If one element has bit 2 set, NO other element in the subarray can have bit 2 set. Each bit position can be claimed by at most one element.
Think of it like a parking lot where each spot can only hold one car. If a number parks in bit position 3, that spot is taken.
Brute Force — Check All Subarrays
Checking every pair in every subarray is O(n³). For n=10⁵, that's10¹⁵ operations — would take years.
✨ The Sliding Window Solution
We use a sliding window with a running OR. The window is "nice" if (windowOR & nums[right]) === 0. If the new number conflicts, we shrink from the left until the conflict resolves.
📊 Dry Run — [1, 3, 8, 48, 10]
Step
Window
windowOR
New num
Conflict?
Action
Max Len
1
[1]
001
1
No
Expand
1
2
[1, 3]
011
3
⚠️ 1&3≠0
Shrink: remove 1
1
3
[3]
011
8
No (3&8=0)
Expand
2
4
[3, 8, 48]
111011
48
No
Expand
3 🎯
5
[3, 8, 48, 10]
111011
10
⚠️ 48&10≠0
Shrink until resolved
3
Warning
⚠️ Important: The XOR-removal trick (windowOR ^= nums[left]) only works because the nice property guarantees no shared bits within the window. In a general sliding window with OR, you cannot simply XOR to remove an element — you'd need a frequency map.
ProblemEmbed: longest-nice-subarray
Problem 4 & 5
4. Bitwise OR of Subarrays — Two Classic Problems
OR has a beautiful property: it only increases. As you OR more numbers, the result can only gain bits. This monotonicity makes two hard problems surprisingly tractable.
Problem 4a: Smallest Subarrays With Maximum Bitwise OR
Problem: For each starting index i, find the minimum length subarray starting at i whose OR equals the maximum possible OR for that start.
🤔 The Key Insight
For a fixed start i, as we extend to the right, the OR only increases. The maximum OR is reached once we've collected every bit that appears somewhere to the right. We scan from right to left, tracking the nearest position where each bit appears.
Key Insight
🔑 The Right-to-Left Pattern: When you need to know "what's the nearest position to the right with a 1 at bit k?", scan from right to left, keeping an arraynextPos[32]. Each iteration updates the bits present in the current number. This pattern appears in MANY bit problems.
Problem 4b: Bitwise ORs of Subarrays
Problem: Count the number of distinct OR values across all possible subarrays.
🔍 Real-Time Thinking — What Do I Know?
"OR only adds bits — it never removes them. So as I extend a subarray, the OR value can only stay the same or increase. For subarrays ending at position i, as I move the start leftward, the OR value monotonically increases. Since there are only 32 bits, each OR value can change at most 32 times! So for each ending position, there are at most 32 distinct OR values. I just need to track the set of OR values for subarrays ending at each position, then OR the next number with each one."
🤔 The Key Insight
For subarrays ending at a fixed position i, as the start moves left, the OR only gains bits. So the set of OR values for subarrays ending ati is small — at most 32 distinct values (since there are only 32 bits to gain).
Tip
⚡ Complexity Analysis: The set prev has at mostO(log MAX) values (≈ 32) because each OR can only add new bits. Once a value reaches all 1s, further ORing doesn't change it. Total complexity:O(32n) — effectively O(n)!
5. Longest Subarray With Maximum AND — The Deceptively Simple One
Problem: Given an array of integers, find the length of the longest contiguous subarray where the bitwise AND equals the maximum possible ANDacross all subarrays.
Note
📏 Real-World Analogy: AND is like a strict teacher — once a student (bit) misbehaves (becomes 0), they're out of the class forever. The maximum possible AND is achieved by the single-element subarray [maxElement], because adding ANY other element can only clear more bits. So the max AND is simply the max element. The problem reduces to finding the longest consecutive run of that max element — it's no longer a bit problem, it's a run-length problem!
🤔 This Looks Hard — But It's NOT
Most people start reaching for segment trees, sliding windows, or sparse tables. But here's the truth: The maximum AND of any subarray is simply the maximum element of the array.
Why? Because a single-element subarray [maxVal] has AND =maxVal. Any larger subarray's AND is ≤ every element in it, which is ≤ the maximum element. So maxVal is both achievable AND the upper bound.
✨ The Solution: Find the Longest Run of the Max Element
Once we know the max AND is maxVal, the problem reduces to: find the longest contiguous run of elements equal to maxVal. That's it. No bit manipulation needed!
📊 Understanding With a Table
Array
Max Element
Longest Run
Answer
[1, 2, 3, 3, 2, 2]
3
[3, 3]
2
[10, 20, 30, 40]
40
[40]
1
[5, 5, 5, 5]
5
[5, 5, 5, 5]
4
[8, 8, 8, 4, 8, 8]
8
[8, 8, 8]
3
Key Insight
🔑 The Meta-Lesson: Sometimes the hardest-looking bit problems have the simplest solutions. The key is understanding the mathematical propertiesof the operation (AND is idempotent, monotonically decreasing) rather than jumping into complex data structures. The max AND is the max element — remember this!
Note
💡 Symmetric Problem: The same reasoning applies tominimum OR subarray. The minimum possible OR of any subarray is the minimum element of the array. The problem becomes finding the longest run of the minimum element.
Problem: Given a binary matrix (0s and 1s), you can flip any row or any column (toggle every bit). The "score" is the sum of the binary values of each row. Maximise the score.
🤔 Why Greedy Works
Each row's value is a binary number. The most significant bit (MSB)of each row contributes 2cols-1 — more than ALL lower bits combined (2cols-1 - 1). So the first priority is making every row's MSB a 1.
Two-Phase Greedy Algorithm
Optimised Score — No Mutation Needed
We can compute the score directly without modifying the matrix:
Tip
⚡ The grid[r][c] === grid[r][0] Trick:After row flips, the effective value of grid[r][c] isgrid[r][c] XOR grid[r][0] (if row was flipped, all bits are inverted). Checking equality is the same as XOR but simpler. If a row's first bit was 0 and we flipped, then grid[r][c] === grid[r][0]means the bit is 1 after flipping.
ProblemEmbed: score-after-flipping-matrix
Interview Prep
🎯 Interview Cheat Sheet
Key Insight
Q1: How do you compute AND of a range [left, right] without iterating? Find the common binary prefix of left and right. Shift both right until they're equal, then shift back. Or use n & (n-1) to clear trailing bits of right until it ≤ left.
Key Insight
Q2: How do you find the largest subset with AND > 0? Count how many numbers have each bit set. The answer is the maximum count across all bit positions. No subset enumeration needed — any subset with AND > 0 must share at least one common bit.
Key Insight
Q3: What is the "Longest Nice Subarray" trick? Use a sliding window with a cumulative OR. A new element fits if(windowOR & nums[r]) === 0. When it doesn't, shrink from left by XOR-ing out elements (safe because no bits overlap in a valid window).
Key Insight
Q4: How do you find all distinct OR values of subarrays? Iterate through the array, maintaining a set of OR values for subarrays ending at each position. For each new number, OR it with every value from the previous set. The set size is bounded by O(log MAX) ≈ 32, giving O(32n) total.
Key Insight
Q5: What's the max AND subarray trick? The maximum AND equals the maximum element in the array. Find the longest consecutive run of that element. That's the answer — no actual AND operations needed!
Key Insight
Q6: How does Score After Flipping Matrix work? Two-phase greedy: (1) Flip rows to make every row's MSB a 1. (2) For each remaining column, flip if it has more 0s than 1s. The MSB dominates the score, so phase 1 comes first.
Key Insight
Q7: What's the key difference between AND and OR in ranges? AND is monotonically decreasing — bits only get cleared. OR is monotonically increasing — bits only get set. AND problems use common-prefix isolation. OR problems use right-to-left next-occurrence tracking.
Summary
📝 Key Takeaways
Range AND = common prefix of the range boundaries. Shift until equal, or use n & (n-1) to clear trailing bits.
Largest AND combination = bit counting: find the bit position with the most numbers that have it set. Max count = answer.
Longest Nice Subarray = sliding window with cumulative OR. Window is "nice" when (windowOR & nextNum) === 0.
OR of subarrays is monotonic — values only increase. Track OR values ending at each position; set size ≤ O(log MAX).
Maximum AND subarray = longest run of max element. The max AND equals the max element of the array.
Score After Flipping Matrix = two-phase greedy: ensure every row's MSB is 1, then maximise 1s per column.
AND shrinks, OR expands across a range. This asymmetry determines the technique: common prefix for AND, right-to-left next-occurrence for OR.
Time: O(n) or O(log n), Space: O(1) — all these patterns are space-optimal.
Practice! — The only way this becomes intuitive is by solving problems. The Playground is your dojo 🥋
Note
🔮 What's Next? Now that you've mastered AND/OR range patterns, head over to Bit Counting to learn about popcount and Hamming distance!
function rangeBitwiseAndBrute(left, right) { let result = left; for (let i = left + 1; i <= right; i++) { result &= i; // AND every number one by one } return result;}// Works for small ranges: rangeBitwiseAndBrute(5, 7) → 4// Fails for large: rangeBitwiseAndBrute(0, 2147483647) → TOO SLOW!
function rangeBitwiseAnd(left, right) { let shift = 0; // Keep shifting right until left and right converge while (left < right) { left >>= 1; right >>= 1; shift++; } // Shift the common prefix back into position return left << shift;}// 📊 Dry Run: rangeBitwiseAnd(5, 7)// Step 1: left=5(101), right=7(111) → 5 < 7 → shift 1// left=2(010), right=3(011) → 2 < 3 → shift 2// left=1(001), right=1(001) → 1 === 1 → STOP!// Result: left << 2 = 1 << 2 = 4 (100₂) ✅
function rangeBitwiseAnd(left, right) { while (left < right) { // Clear the lowest set bit of right right &= right - 1; } return right;}// 📊 Dry Run: rangeBitwiseAnd(12, 15)// right = 15 (1111) → 15 & 14 = 14 (1110) → 14 < 12? No// right = 14 (1110) → 14 & 13 = 12 (1100) → 12 ≤ 12? Yes! STOP// Result: 12 ✅
function largestCombinationBrute(candidates) { // Try ALL subsets? That's 2^n — impossible for large n! // We need a smarter approach.}
function largestCombination(candidates) { let maxCount = 0; // Check each bit position (0 to 31 for 32-bit integers) for (let bit = 0; bit < 32; bit++) { let count = 0; const mask = 1 << bit; for (const num of candidates) { if (num & mask) count++; } maxCount = Math.max(maxCount, count); } return maxCount;}largestCombination([16, 17, 71, 62, 12, 24, 14]); // 4// Bit 3 and bit 0 each have 4 numbers set → answer is 4
function longestNiceSubarrayBrute(nums) { let maxLen = 0; for (let i = 0; i < nums.length; i++) { for (let j = i; j < nums.length; j++) { // Check if EVERY pair in [i..j] has AND = 0 let ok = true; for (let a = i; a <= j && ok; a++) { for (let b = a + 1; b <= j && ok; b++) { if ((nums[a] & nums[b]) !== 0) ok = false; } } if (ok) maxLen = Math.max(maxLen, j - i + 1); } } return maxLen;}// O(n³) — way too slow for large arrays!
function longestNiceSubarray(nums) { let left = 0; let windowOR = 0; let maxLen = 0; for (let right = 0; right < nums.length; right++) { // Shrink window while the new number conflicts while (windowOR & nums[right]) { // Remove nums[left] by XOR — safe because // its bits are unique in the window windowOR ^= nums[left]; left++; } // Add the new number to the window windowOR |= nums[right]; // Update max length maxLen = Math.max(maxLen, right - left + 1); } return maxLen;}longestNiceSubarray([1, 3, 8, 48, 10]); // 3// Longest: [3, 8, 48] — all pairs have AND = 0
function smallestSubarrays(nums) { const n = nums.length; const result = new Array(n).fill(1); // nextPos[bit] = nearest position ≥ i where bit is set const nextPos = new Array(32).fill(Infinity); for (let i = n - 1; i >= 0; i--) { // Update nextPos for bits set in nums[i] for (let bit = 0; bit < 32; bit++) { if (nums[i] & (1 << bit)) { nextPos[bit] = i; } } // Find the farthest nextPos among bits NOT set in nums[i] let farthest = i; for (let bit = 0; bit < 32; bit++) { if (nums[i] & (1 << bit)) continue; // already have this bit if (nextPos[bit] !== Infinity) { farthest = Math.max(farthest, nextPos[bit]); } } result[i] = farthest - i + 1; } return result;}smallestSubarrays([1, 0, 2, 1, 3]);// Output: [3, 3, 2, 2, 1]
function subarrayBitwiseORs(nums) { const distinct = new Set(); let prev = new Set(); // OR values for subarrays ending at previous position for (const num of nums) { // Start with current number alone const curr = new Set([num]); // OR num with every previous ending OR for (const val of prev) { curr.add(val | num); } // Add all to global distinct set for (const val of curr) { distinct.add(val); } prev = curr; } return distinct.size;}subarrayBitwiseORs([1, 2, 4]);// Subarray ORs: 1, 2, 4, 1|2=3, 2|4=6, 1|2|4=7// Distinct: {[1, 2, 4, 3, 6, 7]} → 6subarrayBitwiseORs([1, 1, 2]);// Distinct: {[1, 2, 3]} → 3
function longestSubarray(nums) { const maxVal = Math.max(...nums); let maxLen = 0; let currentLen = 0; for (const num of nums) { if (num === maxVal) { currentLen++; maxLen = Math.max(maxLen, currentLen); } else { currentLen = 0; // reset on any smaller number } } return maxLen;}longestSubarray([1, 2, 3, 3, 2, 2]); // 2 (run of two 3s)longestSubarray([1, 2, 3, 4]); // 1 (single 4)longestSubarray([5, 5, 5, 5]); // 4 (all 5s)longestSubarray([8, 8, 8, 4, 8, 8]); // 3 (first run of 8s)
function matrixScore(grid) { const rows = grid.length; const cols = grid[0].length; // Phase 1: Flip rows to make first column all 1s for (let r = 0; r < rows; r++) { if (grid[r][0] === 0) { for (let c = 0; c < cols; c++) { grid[r][c] ^= 1; // toggle entire row } } } // Phase 2: Flip columns to maximise 1s in each column for (let c = 1; c < cols; c++) { let ones = 0; for (let r = 0; r < rows; r++) { if (grid[r][c] === 1) ones++; } // If more 0s than 1s, flip the column if (ones < rows - ones) { for (let r = 0; r < rows; r++) { grid[r][c] ^= 1; } } } // Calculate score let score = 0; for (let r = 0; r < rows; r++) { let rowVal = 0; for (let c = 0; c < cols; c++) { rowVal = (rowVal << 1) | grid[r][c]; } score += rowVal; } return score;}matrixScore([[0,0,1,1],[1,0,1,0],[1,1,0,0]]); // 39
function matrixScore(grid) { const rows = grid.length; const cols = grid[0].length; // Phase 1: Each row's MSB contributes rows * 2^(cols-1) let score = rows * (1 << (cols - 1)); // Phase 2: For each remaining column, maximise 1s for (let c = 1; c < cols; c++) { let ones = 0; for (let r = 0; r < rows; r++) { // grid[r][c] === grid[r][0] means this bit is 1 after row flip if (grid[r][c] === grid[r][0]) ones++; } // Each 1 in this column contributes 2^(cols-1-c) const maxOnes = Math.max(ones, rows - ones); score += maxOnes * (1 << (cols - 1 - c)); } return score;}matrixScore([[0,0,1,1],[1,0,1,0],[1,1,0,0]]); // 39