What is the time and space complexity of Bitwise AND of Range?

Time complexity: O(log n). Space complexity: O(1).

Bitwise AND of Range

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Bitwise AND of Range

Approach

Right-shift both left and right until they are equal, counting the shifts. The common prefix is the bits shared by all numbers in the range. Shift the prefix back left to restore the original bit positions with zeros filling the lower bits.

Complexity Analysis

Time: O(log n)
Space: O(1)

Pattern

Bit Shifting

Why It Works

Any bit position where left and right differ will have at least one number in the range with a 0 at that position, causing AND to produce 0. Only the shared prefix survives.

Updated Feb 2026