Binary Number with Alternating Bits - Video Solutions

Problem Overview: Given a positive integer n, determine whether its binary representation contains alternating bits. That means every adjacent bit must differ, such as 101010 or 10. If any two neighboring bits are the same (like 110 or 1001), the number does not satisfy the condition.

Approach 1: Observation and Iterative Check (Time: O(log n), Space: O(1))

The straightforward solution inspects bits one by one from right to left. Extract the last bit using n & 1, then shift the number right using n >> 1. Track the previous bit and compare it with the current bit during each iteration. If two consecutive bits match, the pattern breaks and you return false.

This works because each right shift removes the least significant bit, letting you compare neighbors sequentially. The loop runs once for every bit in the number, which is O(log n) since the number of bits grows logarithmically with the value of n. Space remains O(1) because only a few variables are used.

This approach is easy to reason about and shows clear understanding of bit manipulation. It is often the first solution candidates write during interviews.

Approach 2: Bitwise Comparison Trick (Time: O(1), Space: O(1))

A more elegant approach relies on a useful property of alternating bit patterns. If you XOR a number with itself shifted right by one (x = n ^ (n >> 1)), the result becomes a sequence of all 1 bits when the original number had perfectly alternating bits. For example, 1010 ^ 0101 = 1111.

Once you obtain x, check whether it consists only of consecutive 1s. A number with all 1s has the property x & (x + 1) == 0. This works because adding 1 flips the entire run of 1s and introduces a carry into a new bit. If the AND operation returns zero, the pattern is valid.

This method compresses the entire validation into a couple of bit manipulation operations and avoids looping through individual bits. Runtime is effectively O(1) for fixed-width integers, with O(1) space.

Recommended for interviews: Start with the iterative bit check because it clearly demonstrates understanding of binary representation and shifting. After that, mention the XOR trick as an optimization. Interviewers typically expect the n ^ (n >> 1) insight since it shows strong familiarity with bit patterns and low-level operations.