Exactly One Consecutive Set Bits Pair - Video Solutions

Problem Overview: You are given an integer and need to determine whether its binary representation contains exactly one pair of consecutive set bits (11). Multiple pairs or no pairs should return false. The challenge is detecting these adjacent bits efficiently without scanning unnecessary states.

Approach 1: Binary String Scan (O(b) time, O(b) space)

Convert the integer to its binary string form and scan for occurrences of the substring "11". Iterate through the string and increment a counter whenever two adjacent characters are both '1'. If the counter equals exactly one at the end, the condition is satisfied. This approach is easy to reason about and good for quick prototypes, but it allocates extra memory for the string and processes every bit explicitly. The time complexity is O(b) where b is the number of bits in the representation, and space complexity is also O(b).

Approach 2: Bit-by-Bit Scan (O(b) time, O(1) space)

A more typical low-level approach uses bit manipulation. Iterate through the bits using right shifts. At each step, check the lowest two bits using (n & 3). When the value equals 3 (binary 11), you found a consecutive pair. Count such occurrences while shifting the number right by one bit each iteration. If the count ever exceeds one, you can stop early. This avoids string conversion and keeps memory usage constant. Time complexity remains O(b) and space complexity is O(1).

Approach 3: Bitwise Pair Detection with Mask (O(1) time, O(1) space)

The cleanest solution uses a well-known trick from bitwise operations. Compute x = n & (n << 1). This operation aligns each bit with its neighbor, leaving set bits only where consecutive ones exist. For example, if n = 0b10110, shifting left produces 0b101100, and the AND result marks the positions of 11. If there is exactly one consecutive pair, x will contain exactly one set bit. You can verify this using the classic power-of-two check: x != 0 && (x & (x - 1)) == 0. This approach runs in constant time because it performs a fixed number of bit operations and uses constant space.

Recommended for interviews: Start by explaining the straightforward scan to show you understand the definition of consecutive bits. Then present the optimized bit trick using n & (n << 1). Interviewers usually expect the bitwise solution because it demonstrates strong understanding of bit manipulation patterns and constant-time reasoning.