201. Bitwise AND of Numbers Range

NeetCode: Bitwise AND of Numbers Range · LeetCode: 201. Bitwise AND of Numbers Range · Difficulty: Medium

Given two integers left and right with 0 <= left <= right <= 2^31 - 1, return the bitwise AND of all numbers in the inclusive range [left, right].

Example

Input:  left = 5, right = 7     Output: 4    (101 & 110 & 111 = 100)
Input:  left = 0, right = 0     Output: 0
Input:  left = 1, right = 2147483647    Output: 0

Brute force: AND them all

Start with left and AND in every following number. The loop can stop once the result reaches zero, since it cannot become non-zero again. For a range such as [2^30, 2^31 - 1] the result stays non-zero for a long time.

The loop counter is a long. With an int counter and right = Integer.MAX_VALUE, x++ would wrap to Integer.MIN_VALUE, the condition x <= right would stay true, and the AND with the negative value would give a wrong result.

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int acc = left;
        for (long x = left; x <= right; x++) {
            acc &= (int) x;
            if (acc == 0) {
                break;
            }
        }
        return acc;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rangeBitwiseAnd(5, 7));
        System.out.println(s.rangeBitwiseAnd(0, 0));
        System.out.println(s.rangeBitwiseAnd(6, 7));
        System.out.println(s.rangeBitwiseAnd(Integer.MAX_VALUE, Integer.MAX_VALUE));
    }
}

4
0
6
2147483647

Time: O(right - left). Space: O(1).

Optimal: common binary prefix

A bit survives the AND only if it is 1 in every number of the range. Counting up from left to right, every bit position that changes at least once in the range will be 0 at some point, so it is 0 in the result. The bits that never change are exactly the common leading prefix of left and right in binary. So shift both numbers right until they are equal (counting the shifts), then shift the common prefix back.

5 = 101, 7 = 111  ->  shift once: 10 vs 11  ->  shift twice: 1 vs 1  (equal, 2 shifts)
result = 1 << 2 = 100 = 4

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shift++;
        }
        return left << shift;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.rangeBitwiseAnd(5, 7));
        System.out.println(s.rangeBitwiseAnd(0, 0));
        System.out.println(s.rangeBitwiseAnd(1, 2147483647));
        System.out.println(s.rangeBitwiseAnd(6, 7));
        System.out.println(s.rangeBitwiseAnd(Integer.MAX_VALUE, Integer.MAX_VALUE));
    }
}

4
0
0
6
2147483647

Time: O(log right), at most 31 iterations. Space: O(1).

The inputs are non-negative, so >> (which copies the sign bit) never brings in a 1, and left << shift restores at most the original bit width, so it cannot overflow.