Welcome to Subscribe On Youtube

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

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)$.

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}

  • 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;
}

All Problems

All Solutions