AND In Range

JavaView on GFG

Intuition

Bitwise AND of all numbers from L to R. Common prefix of L and R in binary.

Algorithm

1While L != R: R >>= 1, L >>= 1, count shifts. Answer = L << count.

Common Pitfalls

•Same as LC 201. Shift both right until equal (find common prefix). Shift result back left.

AND In Range.java

Java

// Approach: Bit manipulation. The AND of all numbers in [l, r] keeps only common prefix bits.
// Right-shift both numbers until they are equal, tracking the shift count, then shift back.
// Time: O(log n) Space: O(1)
class Solution {
    public int andInRange(int l, int r) {
        // Answer will be the common part of binary l and r from msb. As all other will
        // give zero for & operation which are not common.
        int count = 0; // will store the number of bits removed from lsb
        while (l != r) {
            l >>= 1; // remove a bit from left
            r >>= 1; // remove a bit from left
            count++; // update removed count
        }
        
        return l << count; // add zeroes to right after common part
    }
}

Was this solution helpful?