#693

Easy

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Binary Number with Alternating Bits

Check whether a given integer has alternating bits using a bit manipulation approach.

Problem Statement

Given a positive integer, determine if its binary representation has alternating bits. The binary form of the number should have no two adjacent bits with the same value.

For example, the binary representation of 5 (which is '101') alternates between 1s and 0s. Conversely, the binary representation of 7 ('111') does not, as it has consecutive 1s.

Examples

Example 1

Input: n = 5

Output: true

The binary representation of 5 is: 101

Example 2

Input: n = 7

Output: false

The binary representation of 7 is: 111.

Example 3

Input: n = 11

Output: false

The binary representation of 11 is: 1011.

Constraints

1 <= n <= 231 - 1

Solution Approach

Bitwise XOR Approach

A simple bitwise trick involves XORing the number with itself right-shifted by 1. If the result is a number where all bits are 1, the original number had alternating bits.

Masking and Comparison

Another approach is to check if the number when right-shifted by 1 and XORed with the original number results in a number with all bits set to 1. This can be checked using a bitwise AND operation.

Efficient Time Complexity

This solution works in constant time, O(1), because it only involves a few bitwise operations without the need for loops or recursion.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

The solution is optimized with a time complexity of O(1) since it only requires a constant number of bitwise operations. The space complexity is also O(1), as no additional memory is used aside from a few variables.

What Interviewers Usually Probe

Look for a clear understanding of bit manipulation techniques, especially XOR and bitwise AND operations.
Expect the candidate to explain the constant time complexity and why this is efficient for the given problem.
Be cautious of candidates who try to overcomplicate the problem with loops or other approaches.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the bitwise XOR operation and applying it incorrectly.
Assuming that the number should have an even number of bits, instead of focusing on alternating 1s and 0s.
Not recognizing the need for constant time solutions when the problem constraints allow it.

Follow-up variants

Implement the solution for negative numbers and edge cases (e.g., minimum values).
Adapt the solution to check for alternating bits in a given range of numbers.
Optimize the solution further if the problem's constraints change.

FAQ

What is the main approach to solving the Binary Number with Alternating Bits problem?

The main approach uses bitwise operations like XOR to check if the binary representation alternates between 1s and 0s.

How do I use XOR to solve this problem?

XOR the number with itself right-shifted by 1 and check if the result equals a number with all bits set to 1, which would confirm alternating bits.

Why is the solution for Binary Number with Alternating Bits O(1)?

The solution only involves a constant number of bitwise operations, regardless of the size of the input number.

What is the bitwise AND operation used for in this problem?

The bitwise AND operation helps verify if all bits of the result from XOR are set to 1, which is necessary to confirm alternating bits.

What are the common pitfalls to avoid in solving the Binary Number with Alternating Bits problem?

Avoid overcomplicating the solution with loops, incorrectly using bitwise operations, or misunderstanding the alternating pattern.

terminal

Solution

Solution 1: Simulation

We cyclically right-shift $n$ until it becomes $0$, checking whether the binary bits of $n$ appear alternately. If during the loop we find that $0$ and $1$ do not appear alternately, we directly return $\textit{false}$. Otherwise, when the loop ends, we return $\textit{true}$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = -1
        while n:
            curr = n & 1
            if prev == curr:
                return False
            prev = curr
            n >>= 1
        return True

Solution 2: Bit Manipulation

Assuming $\text{01}$ appears alternately, we can convert all trailing bits to $\text{1}$ through misaligned XOR. Adding $\text{1}$ gives us a power of $2$, which is a number $n$ (where $n$ has only one bit that is $\text{1}$). Then, using $\text{n} \& (\text{n} + 1)$ can eliminate the last $\text{1}$ bit.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = -1
        while n:
            curr = n & 1
            if prev == curr:
                return False
            prev = curr
            n >>= 1
        return True

Continue Practicing

#691 stickers to spell word #698 partition to k equal sum subsets #672 bulb switcher ii