Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the maximum a ^ b for all pairs with l ≤ a ≤ b ≤ r. Brute force tries every pair in the range: O((r−l)²), fine when the range is tiny. The closed form is the real insight: let d = l ^ r and let p be the position of its highest set bit; the answer is 2^(p+1) − 1, i.e. all ones up to and including bit p. Because l and r differ first at bit p, you can always pick two numbers in [l, r] that differ in bit p and in every lower bit — making the XOR a solid block of ones.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can move past the obvious double loop to the closed form, and explain WHY the most significant differing bit between l and r fixes the answer to a block of ones.
Where candidates slip
Only writing the O((r−l)²) loop without the insight, mishandling l == r (returning a garbage max instead of 0), or computing 2^p − 1 instead of 2^(p+1) − 1 (off-by-one on the bit width).
How to stand out
Give the brute force, then derive the closed form: d = l ^ r, p = its top set bit, answer = 2^(p+1) − 1, and justify that the range is wide enough to realize all-ones below p.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMax a XOR b, l<=a<=b<=rRange tiny?YesAlwaysExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Double Loop Over the Range
1Hint 1Explore hintHide hint
The constraint is l ≤ a ≤ b ≤ r. What's the most direct way to find the best pair? Try them all.
2Hint 2Explore hintHide hint
Two nested loops: a from l to r, b from a to r. Compute a ^ b and keep the maximum.
3Hint 3Explore hintHide hint
Start b at a (not a+1) so the a == b case is included — it gives 0 and matters when l == r.
A · Core idea
Enumerate every valid pair and keep the largest XOR.
Why it's the natural first attempt. The problem fully specifies the search space: all (a, b) with l ≤ a ≤ b ≤ r. Two nested loops walk exactly that set, and a ^ b is computed directly. Correct with zero cleverness.
Why `b` starts at `a`. The constraint allows a == b. Starting b at a includes those pairs (each contributing 0) and avoids re-checking (a, b) and (b, a) separately. When l == r the only pair is (l, l) → the loop correctly returns 0.
Why it's good enough here. With r ≤ 1000, the range is at most ~1000 wide, so the double loop is well under a million operations. It passes comfortably. But it hides the structure of the answer — the next approach computes the same result in O(1) and explains the 'block of ones' shape.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
l = 10, r = 15Interactive diagram
Pairwise enumeration
a=10, b=10The upper-triangular set of pairs (a ≤ b) the loops visit.
7C · Code with teaching comments
Reference implementation previewpublic int maximizingXor(int l, int r) { int best = 0; for (int a = l; a <= r; a++) { for (int b = a; b <= r; b++) { // b starts at a so a == b is allowed best = Math.max(best, a ^ b);Explore the full codeHide the full code
D · Why it works and complexityO((r−l)²) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The double loop is acceptable only because the range is tiny. The moment the range grows, you need the closed form — so it's worth understanding why the answer is always a run of low-order ones.
ComplexityO((r−l)²) time, O(1) space — About (r−l)²/2 pairs, each an O(1) XOR. With r−l ≤ 1000 that's ~5×10⁵ operations — instant.
E · Edge cases and pitfalls3Starting b at a+1 — drops the a == b case so l == r would return a wrong/initial value.Explore edge casesHide edge cases
Pitfalls
- Starting b at a+1 — drops the a == b case so l == r would return a wrong/initial value.
- Initializing best to a negative sentinel when 0 is the natural floor for XOR.
- Relying on the double loop when the range could be large — it won't scale.
Approach 2 of 2 · Optimal
Leading Differing Bit — Closed Form (Optimal)
1Hint 1Explore hintHide hint
XOR is maximized by differing in the highest possible bits. Where do l and r first differ? Compute l ^ r.
2Hint 2Explore hintHide hint
Let p be the position of the most significant set bit of l ^ r. Across bit p, the range [l, r] contains numbers covering every pattern of bits 0..p.
3Hint 3Explore hintHide hint
So you can pick a pair differing in all of bits 0..p → XOR = all ones there = 2^(p+1) − 1.
A · Core idea
Compute the answer directly from the endpoints.
Step 1: where do l and r differ? Look at d = l ^ r. Its set bits are exactly the positions where l and r disagree. Let p be the most significant such position.
Step 2: why bit p is reachable. Above bit p, l and r are identical, so every number in [l, r] shares those high bits — no XOR gain possible there. At bit p, l has a 0 and r has a 1 (or vice versa). Because the range crosses that boundary, it includes a number of the form …0 111…1 (just below the boundary) and …1 000…0 (the boundary itself). Concretely, the range is wide enough to contain two values that differ in bit p AND in every bit below it.
Step 3: the answer. The maximum XOR therefore has ones in bits p, p−1, …, 0 and zeros above. A run of p+1 ones equals 2^(p+1) − 1. That's the closed form.
Why not 2^p − 1. Bits 0 through p inclusive are p+1 ones, not p. Using 2^p − 1 would drop the top bit of the answer — the classic off-by-one. And if l == r, then d = 0, there is no differing bit, and the answer is 0.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
l = 10, r = 15Interactive diagram
From differing bit to all ones
xorThe top differing bit p forces the answer to be a solid block of ones below it.
7C · Code with teaching comments
D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Maximizing XOR over a contiguous range is governed entirely by the leading bit where the two bounds split. Once they split at bit p, the range is rich enough to realize all ones beneath p — so the answer is the fixed shape 2^(p+1) − 1, computable in O(1).
ComplexityO(1) time, O(1) space — One XOR plus finding the top set bit (a single built-in or a short shift loop) — constant time and space, independent of the range size.
E · Edge cases and pitfalls6l = 8, r = 8 — d = 0 → return 0; the only allowed pair is (8, 8).Explore edge casesHide edge cases
Edge cases handled
l = 8, r = 8d = 0 → return 0; the only allowed pair is (8, 8).l = 1, r = 2d = 1 ^ 2 = 3 (11), top bit p = 1 → 2² − 1 = 3, achieved by 1 ^ 2.l = 5, r = 6d = 3 (011), p = 1 → 3; matches 5 ^ 6 = 3.
Pitfalls
- Returning 2^p − 1 instead of 2^(p+1) − 1 — off-by-one that drops the leading bit.
- Forgetting the l == r case where d == 0 and the answer must be 0.
- Computing the lowest set bit instead of the highest — the MOST significant differing bit decides the answer.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int maximizingXor(int l, int r) { int d = l ^ r; if (d == 0) return 0; // l == r → only pair is (l, l) int p = 31 - Integer.numberOfLeadingZeros(d); // index of top set bit return (1 << (p + 1)) - 1; // all ones in bits 0..pExplore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Off-by-one on the bit width
Bits 0..p inclusive are p+1 ones. Using 2^p − 1 produces only p ones and undercounts the maximum by the leading bit.
Explore the code comparisonHide the code comparison
Off-by-one on the bit width
Bits 0..p inclusive are p+1 ones. Using 2^p − 1 produces only p ones and undercounts the maximum by the leading bit.
Don't write this
p = (l ^ r).bit_length() - 1
return (1 << p) - 1 # missing the top bitWrite this instead
p = (l ^ r).bit_length() - 1
return (1 << (p + 1)) - 1 # includes bit p2Missing the l == r guard
When l == r, l ^ r == 0 and there is no most-significant set bit; computing a bit index on 0 is meaningless. The answer is simply 0.
Explore the code comparisonHide the code comparison
Missing the l == r guard
When l == r, l ^ r == 0 and there is no most-significant set bit; computing a bit index on 0 is meaningless. The answer is simply 0.
Don't write this
int p = 31 - Integer.numberOfLeadingZeros(l ^ r);
return (1 << (p + 1)) - 1; // wrong/garbage when l == rWrite this instead
int d = l ^ r;
if (d == 0) return 0;
int p = 31 - Integer.numberOfLeadingZeros(d);
return (1 << (p + 1)) - 1;3Using the lowest differing bit
The maximum XOR is driven by the MOST significant differing bit, not the least. Taking the low bit gives a far smaller answer.
Explore the code comparisonHide the code comparison
Using the lowest differing bit
The maximum XOR is driven by the MOST significant differing bit, not the least. Taking the low bit gives a far smaller answer.
Don't write this
d = l ^ r
p = (d & -d).bit_length() - 1 # lowest set bit
return (1 << (p + 1)) - 1Write this instead
d = l ^ r
p = d.bit_length() - 1 # highest set bit
return (1 << (p + 1)) - 1Revise
Carry the pattern into the interview
Pattern to remember
Leading differing bit → all-ones below it
Code pattern to memorize
if l == r: return 0
d = l ^ r # bits where l and r differ
p = highestSetBitIndex(d) # most significant differing bit
return (1 << (p + 1)) - 1 # 2^(p+1) - 1 = all ones up to bit pRules to remember
- 1The maximum XOR is decided by the most significant bit where l and r differ — call its position p.
- 2Once l and r differ at bit p, the range [l, r] is wide enough to hit every combination of the lower p bits, so the best XOR is all ones from bit p down to bit 0.
- 3All ones in bits 0..p equals
2^(p+1) − 1— that single expression is the whole answer. - 4If
l == rthe only pair is (l, l) andl ^ l = 0. - 5Brute force is acceptable here because the range is small (≤ ~1000), but stating the closed form shows you understand WHY the answer looks like 0…011…1.
Use this pattern when
- Maximize XOR over a contiguous integer range [l, r]
- You can reason about the leading bit where two bounds diverge
- Small ranges where O((r−l)²) is acceptable but you still want the elegant form
- Any 'highest bit that differs decides the answer' style argument
Choose another pattern when
- Partner comes from an arbitrary set, not a contiguous range → bit trie (Maximum Xor), not this formula
- You need the actual pair (a, b), not just the value → reconstruct from p, don't only return the number
- Range is huge AND you need per-query speed → use the O(1) closed form, never the double loop
- Constraint is a ≤ b but with extra filters → the clean closed form may not hold
Interview takeaway
Maximum XOR over a range collapses to one fact: find the top bit where l and r disagree, then the answer is all ones up to that bit (2^(p+1) − 1). The double loop works for small ranges, but the leading-bit closed form is O(1) and explains the structure.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternLeading-differing-bit closed form. For XOR maximization over a contiguous range, the most significant bit where the two bounds diverge forces the answer to 2^(p+1) − 1. Recognize 'range + maximize XOR' as an O(1) bit argument, not a search.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximum XorWhen the partner comes from an arbitrary set instead of a contiguous range, use a binary trie with greedy opposite-bit descent.
- Maximum XOR of Two Numbers in an ArrayComing soonNo range structure to exploit — fall back to the bit trie for arbitrary numbers.
- Sum vs XORAnother endpoint-driven counting trick where the bit pattern of n determines the answer directly.