3950. Exactly One Consecutive Set Bits Pair

EasyBit Manipulation

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer n.

Your task is to look at the binary representation of n and determine whether it contains exactly one pair of consecutive set bits.

A set bit is a bit whose value is 1. A pair of consecutive set bits means two 1s that sit right next to each other in the binary form of n (for example, in 110, the two leftmost bits form one such pair).

Return true if the binary representation of n contains exactly one pair of consecutive set bits, and false otherwise.

For instance:

If n = 3, its binary form is 11, which contains exactly one pair of consecutive set bits, so the answer is true.
If n = 7, its binary form is 111. Here the first and second bits form a pair, and the second and third bits form another pair, giving more than one pair, so the answer is false.
If n = 5, its binary form is 101, which has no two 1s next to each other, so the answer is false.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

Bitwise operations and binary representation properties solve the problem directly.

Open in Flowchart

Intuition

To decide whether the binary form of n has exactly one pair of consecutive set bits, we need to scan the bits one by one and count how many times two adjacent 1s appear.

The key observation is that a pair of consecutive set bits only depends on the current bit and the bit right before it. So while walking through the bits, if we always remember the previous bit, we can check at each step whether the previous bit and the current bit are both 1. Whenever both are 1, we have found one pair.

Since we want exactly one such pair, we cannot simply stop at the first pair we find. We must keep track of whether a pair has already been seen. If we encounter a second pair, we can immediately conclude the answer is false. If, by the end of the scan, we have found one and only one pair, the answer is true; if we found none, the answer is also false.

This naturally leads to processing the bits from the lowest to the highest using n & 1 to read the current bit and n >> 1 to move to the next bit, while maintaining two helper variables: one for the previous bit and one for whether a pair has already been recorded.

Solution Approach

Solution 1: Simulation

We use a variable pre to record the digit of the previous bit, initialized to pre = 0, and another variable vis to record whether a pair of consecutive set bits has already been found, initialized to vis = false.

We iterate through each binary bit of n from the lowest bit to the highest. At each step, we extract the current binary bit using cur = n & 1.

If pre = cur = 1, it means the previous bit and the current bit are both set, so we have found a pair of consecutive set bits. At this moment:

If vis is already true, it indicates that there are multiple pairs of consecutive set bits, so we directly return false.
Otherwise, we set vis = true to record that we have found our first pair.

After handling the current bit, we update pre = cur to remember the current bit for the next iteration, and shift n to the right by one position using n = n >> 1 to process the next bit.

When the loop ends (i.e., n becomes 0), if vis = true, it means exactly one pair of consecutive set bits was found, so we return true; otherwise, we return false.

The time complexity is O(log n), where n is the given integer, since we process each bit of n once. The space complexity is O(1), as we only use a constant number of extra variables.

Example Walkthrough

Let's trace through the solution with n = 6, whose binary representation is 110. This should return true since it contains exactly one pair of consecutive set bits (the two leftmost 1s).

We initialize our helper variables:

pre = 0 (no previous bit yet)
vis = false (no pair found yet)

Now we process the bits from lowest to highest:

Iteration 1: n = 6 (binary 110)

Extract current bit: cur = 6 & 1 = 0
Check pair condition: pre = 0 and cur = 0, so they are not both 1. No pair found.
Update previous bit: pre = cur = 0
Shift right: n = 6 >> 1 = 3 (binary 11)

Iteration 2: n = 3 (binary 11)

Extract current bit: cur = 3 & 1 = 1
Check pair condition: pre = 0 and cur = 1, so they are not both 1. No pair found.
Update previous bit: pre = cur = 1
Shift right: n = 3 >> 1 = 1 (binary 1)

Iteration 3: n = 1 (binary 1)

Extract current bit: cur = 1 & 1 = 1
Check pair condition: pre = 1 and cur = 1, both are 1! We found a pair.
- Since vis is currently false, this is our first pair, so we set vis = true.
Update previous bit: pre = cur = 1
Shift right: n = 1 >> 1 = 0

Loop ends because n = 0.

Final check: vis = true, meaning exactly one pair of consecutive set bits was found, so we return true. ✓

To contrast, consider n = 7 (binary 111). When scanning, we would find a pair at the bits (1,1) setting vis = true, and then find a second pair at the next adjacent (1,1). Since vis is already true when the second pair appears, we immediately return false, correctly rejecting it for having more than one pair.

Solution Implementation

1class Solution:
2    def consecutiveSetBits(self, n: int) -> bool:
3        previous_bit = 0          # the bit examined in the prior iteration
4        found_pair = False        # whether an adjacent pair of set bits was seen
5        while n:
6            current_bit = n & 1   # extract the least-significant bit
7            # detect two consecutive set bits (previous and current both 1)
8            if previous_bit == current_bit == 1:
9                if found_pair:
10                    # a second adjacent set-bit pair invalidates the condition
11                    return False
12                found_pair = True
13            previous_bit = current_bit   # shift the "window" forward
14            n >>= 1                       # move to the next bit
15        return found_pair
16

1class Solution {
2    /**
3     * Scans the binary representation of n from the lowest bit to the highest bit.
4     * Detects pairs of adjacent set bits (two consecutive 1s).
5     * Returns true only if exactly one such pair-triggering event is found;
6     * returns false if no such event occurs or if it occurs more than once.
7     *
8     * @param n the input number to inspect
9     * @return whether exactly one adjacent-set-bit event is detected
10     */
11    public boolean consecutiveSetBits(int n) {
12        // Marks whether an adjacent-set-bit event has already been seen.
13        boolean found = false;
14
15        // previousBit holds the value of the bit examined in the prior iteration.
16        for (int previousBit = 0; n > 0; n >>= 1) {
17            // Extract the current least significant bit.
18            int currentBit = n & 1;
19
20            // Trigger when the previous bit and the current bit are both 1.
21            if (previousBit == currentBit && currentBit == 1) {
22                // A second occurrence means the result is invalid.
23                if (found) {
24                    return false;
25                }
26                // Record the first occurrence.
27                found = true;
28            }
29
30            // Advance: the current bit becomes the previous bit for the next step.
31            previousBit = currentBit;
32        }
33
34        // True only if exactly one adjacent-set-bit event was detected.
35        return found;
36    }
37}
38

1class Solution {
2public:
3    bool consecutiveSetBits(int n) {
4        // Tracks whether we have already recorded one pair of adjacent set bits.
5        bool foundPair = false;
6
7        // Scan the bits of n from least significant to most significant.
8        for (int previousBit = 0; n > 0; n >>= 1) {
9            int currentBit = n & 1;
10
11            // Detect two adjacent bits that are both 1.
12            if (previousBit == currentBit && currentBit == 1) {
13                // If a pair was already found, the run extends or repeats,
14                // which is not allowed, so reject.
15                if (foundPair) {
16                    return false;
17                }
18                // Record the first occurrence of an adjacent set-bit pair.
19                foundPair = true;
20            }
21
22            // Move the window forward: current bit becomes the previous bit.
23            previousBit = currentBit;
24        }
25
26        // Return true only if exactly one isolated pair of set bits was found.
27        return foundPair;
28    }
29};
30

1/**
2 * Determines whether the binary representation of `n` contains
3 * exactly one isolated pair of two consecutive set bits.
4 *
5 * Behavior notes (preserved from original):
6 * - Returns true only if a single consecutive `11` pattern is found.
7 * - A run of three or more set bits (e.g. 111) yields false, because
8 *   it produces more than one adjacent `11` match.
9 * - Returns false if no consecutive set bits exist at all.
10 *
11 * @param n - The non-negative integer to inspect.
12 * @returns true if exactly one pair of consecutive set bits is present.
13 */
14function consecutiveSetBits(n: number): boolean {
15    // Tracks whether a consecutive pair of set bits has already been seen.
16    let hasSeenPair = false;
17
18    // Holds the previously examined bit; initialized to 0.
19    let previousBit = 0;
20
21    // Iterate over each bit of `n`, shifting right until all bits are processed.
22    for (; n > 0; n >>= 1) {
23        // Extract the current least-significant bit.
24        const currentBit = n & 1;
25
26        // Detect two adjacent set bits (previous and current are both 1).
27        if (previousBit === currentBit && currentBit === 1) {
28            // A second consecutive pair invalidates the condition.
29            if (hasSeenPair) {
30                return false;
31            }
32            // Record that the first consecutive pair has been found.
33            hasSeenPair = true;
34        }
35
36        // Advance: the current bit becomes the previous bit for the next step.
37        previousBit = currentBit;
38    }
39
40    // True only when exactly one consecutive pair was encountered.
41    return hasSeenPair;
42}
43

Time and Space Complexity

Time Complexity: O(log n). The while loop continues as long as n is non-zero, and in each iteration n is right-shifted by one bit via n = n >> 1. This means the number of iterations equals the number of bits in n, which is O(log n). All operations inside the loop (bitwise AND, comparisons, assignments) take constant time, so the overall time complexity is O(log n).
Space Complexity: O(1). The algorithm only uses a fixed number of auxiliary variables (pre, vis, cur), regardless of the size of n. No additional data structures that scale with the input are used, so the space complexity is constant.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Returning `True` Immediately After Finding the First Pair

A frequent mistake is to return True as soon as the first pair of consecutive set bits is detected, instead of continuing to scan the remaining bits.

# WRONG
class Solution:
    def consecutiveSetBits(self, n: int) -> bool:
        previous_bit = 0
        while n:
            current_bit = n & 1
            if previous_bit == current_bit == 1:
                return True       # ❌ returns too early
            previous_bit = current_bit
            n >>= 1
        return False

Why it fails: The problem requires exactly one pair, not at least one. For n = 7 (111), this buggy version detects the first adjacent pair and returns True, but the correct answer is False because there are two pairs.

Solution: Keep iterating through all the bits. Use a boolean flag (found_pair) to record that a pair has been seen, and return False the moment a second pair appears. Only after the loop completes should you return the flag's value, as the reference solution does.

Pitfall 2: Mis-handling Overlapping Pairs in `111...`

When three or more 1s appear in a row, the pairs overlap. For 111, the bits at positions (0,1) and (1,2) form two distinct pairs. A subtle error is to think a run of three 1s is "one block" and therefore "one pair."

Why it fails: The problem counts adjacent-bit pairs, not maximal runs of 1s. A run of length k contributes k - 1 pairs. So 111 (run length 3) yields 2 pairs → False.

Solution: Compare each bit with its immediate predecessor (the sliding-window approach). This naturally counts each overlapping pair separately. The condition previous_bit == current_bit == 1 triggers once per adjacent pair, correctly catching the second pair in 111.

Pitfall 3: Incorrect Initialization of `previous_bit`

Initializing previous_bit to 1 (instead of 0) can create a phantom pair if the least-significant bit is also 1.

# WRONG
previous_bit = 1   # ❌ may falsely pair with the first real bit

Why it fails: For n = 3 (11), the first extracted bit is 1. With previous_bit = 1, the very first comparison falsely registers a pair before any real adjacency exists, throwing off the count.

Solution: Initialize previous_bit = 0. Since there is no bit before the least-significant one, treating the imaginary "prior" bit as 0 ensures no false pair is created at the start.

Pitfall 4: Forgetting That `n` Could Be `0`

If n = 0, its binary form is 0, which contains no set bits and thus no pairs.

Why it fails: Some implementations assume n always has at least one bit and skip the empty-input case.

Solution: The while n: loop body never executes for n = 0, and found_pair remains False, so the function correctly returns False. This is handled gracefully by the reference solution without special-casing.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: