What is the time and space complexity of Alternating Bits?

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

Alternating Bits

Easy

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: Alternating Bits

Approach

XOR n with n >> 1. If bits alternate, adjacent bits always differ, so the XOR produces all 1s. Verify the result is all 1s by checking xor & (xor + 1) === 0, which is true only for numbers of the form 2^k - 1.

Complexity Analysis

Time: O(1)
Space: O(1)

Pattern

XOR Pattern

Why It Works

Alternating bits like 101 shifted right gives 010, and XOR of these is 111 (all ones). A non-alternating pattern produces at least one 0 in the XOR result.

Updated Mar 2026