Skip to content

3950. Exactly One Consecutive Set Bits Pair

Description

You are given an integer n.

Return true if its binary representation contains exactly one adjacent pair of set bits, and false otherwise.

 

Example 1:

Input: n = 6

Output: true

Explanation:

  • Binary representation of 6 is 110.
  • There is exactly one adjacent pair of set bits ("11"). Thus, the answer is true​​​​​​​.

Example 2:

Input: n = 5

Output: false

Explanation:

  • Binary representation of 5 is 101.
  • There is no adjacent pair of set bits. Thus, the answer is false​​​​​​​.

 

Constraints:

  • 0 <= n <= 105

Solutions

Solution 1: Simulation

Thinking

We only need the binary representation to contain adjacent ones exactly once. Peel \(\textit{cur}\) from the low bit and compare it with \(\textit{pre}\): both one records a pair, and a second pair fails.

After the scan \(\textit{vis}\) is true iff exactly one consecutive-ones pair occurred. \(n\le 10^5\), so there are few bits.

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

Iterate through each binary bit of \(n\), and denote the current binary bit as \(\textit{cur}\). If \(\textit{pre} = \textit{cur} = 1\), and if \(\textit{vis} = \text{true}\) at this moment, it indicates that there are multiple pairs of consecutive set bits, so we directly return \(\text{false}\). Otherwise, we set \(\textit{vis}\) to \(\text{true}\). Then, we update \(\textit{pre} = \textit{cur}\) and continue to iterate through the next binary bit.

After the iteration ends, if \(\textit{vis} = \text{true}\), return \(\text{true}\); otherwise, return \(\text{false}\).

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def consecutiveSetBits(self, n: int) -> bool:
        pre = 0
        vis = False
        while n:
            cur = n & 1
            if pre == cur == 1:
                if vis:
                    return False
                vis = True
            pre = cur
            n = n >> 1
        return vis

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public boolean consecutiveSetBits(int n) {
        boolean vis = false;
        for (int pre = 0; n > 0; n >>= 1) {
            int cur = n & 1;
            if (pre == cur && cur == 1) {
                if (vis) {
                    return false;
                }
                vis = true;
            }
            pre = cur;
        }
        return vis;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool consecutiveSetBits(int n) {
        bool vis = false;
        for (int pre = 0; n > 0; n >>= 1) {
            int cur = n & 1;
            if (pre == cur && cur == 1) {
                if (vis) {
                    return false;
                }
                vis = true;
            }
            pre = cur;
        }
        return vis;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func consecutiveSetBits(n int) bool {
    vis := false
    for pre := 0; n > 0; n >>= 1 {
        cur := n & 1
        if pre == cur && cur == 1 {
            if vis {
                return false
            }
            vis = true
        }
        pre = cur
    }
    return vis
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function consecutiveSetBits(n: number): boolean {
    let vis = false;
    for (let pre = 0; n > 0; n >>= 1) {
        const cur = n & 1;
        if (pre === cur && cur === 1) {
            if (vis) {
                return false;
            }
            vis = true;
        }
        pre = cur;
    }
    return vis;
}

Comments