Is Bitwise AND of Numbers Range easy or hard?

The problem is classified as Medium because the brute-force idea is simple but inefficient. The challenge lies in recognizing that only the common binary prefix of the range contributes to the final result, which requires understanding bit manipulation patterns.

Bitwise AND of Numbers Range Python/Java solution

Most implementations use a loop that right-shifts both left and right until they become equal, counting the shifts. Afterward, the result is reconstructed with a left shift. This logic is identical across Python, Java, C++, C#, and JavaScript because it relies on standard bitwise operators.

How to solve Bitwise AND of Numbers Range in O(n)?

A straightforward approach iterates from left to right and continuously applies the AND operator: result &= current_number. This works but can be extremely slow when the range is large. Optimized solutions avoid iteration by analyzing binary prefixes instead.

What is the best approach for Bitwise AND of Numbers Range?

The optimal approach finds the common binary prefix between left and right. The common implementation repeatedly right-shifts both numbers until they match, then restores the prefix with left shifts. This runs in O(log n) time where n is the maximum value of the range and uses O(1) space.

Is Bitwise AND of Numbers Range asked at Google/Amazon/Meta?

Bit manipulation range problems like this appear frequently in interviews at companies such as Google, Amazon, and Meta. The problem tests understanding of binary representation and recognizing patterns where brute force can be replaced with bit-level reasoning.

What data structure is used in Bitwise AND of Numbers Range?

No special data structure is required. The solution relies on bit manipulation operations such as shifting and masking to analyze the binary representation of integers. The algorithm operates directly on primitive integer values.

What is the time complexity of Bitwise AND of Numbers Range?

The optimal solution runs in O(log n) time because it processes at most the number of bits in the integers (typically 32). Each iteration removes one differing bit until both numbers share the same prefix. Space complexity remains O(1).

Description Solution Video 12:42

201. Bitwise AND of Numbers Range

Medium49.4% acceptance5 companies

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

0 <= left <= right <= 2³¹ - 1

Asked at 5 companies

Google Amazon Microsoft Meta Bloomberg

Topics

Bit Manipulation

12:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

201. Bitwise AND of Numbers Range

Asked at 5 companies

Topics

Similar problems