LeetCode 693 - Binary Number with Alternating Bits

The problem asks us to determine whether the binary representation of a given positive integer n has alternating bits. In other words, for the binary digits of n, no two consecutive bits should be the same.

leetcodeeasybit-manipulation

LeetCode Problem 693

Difficulty: 🟢 Easy
Topics: Bit Manipulation

Solution

Problem Understanding

The problem asks us to determine whether the binary representation of a given positive integer n has alternating bits. In other words, for the binary digits of n, no two consecutive bits should be the same. For example, 101 is alternating, while 111 is not because it contains consecutive ones.

The input n is guaranteed to be a positive integer within the range 1 <= n <= 2^31 - 1, which corresponds to a 32-bit signed integer range. This constraint ensures that n can be safely handled using standard integer types in Python or Go without overflow.

The expected output is a boolean: true if n has alternating bits and false otherwise.

Important edge cases include the smallest possible input n = 1, which trivially has alternating bits, numbers with all ones (e.g., 7), and numbers with alternating bits ending in 0 or 1.

Approaches

The brute-force approach is straightforward. We can repeatedly extract the least significant bit of the number and compare it with the previous bit. If any two consecutive bits are the same, we return false. Otherwise, we continue until all bits are checked. This approach is correct because it directly verifies the definition of alternating bits, but it may perform up to 32 comparisons for a 32-bit integer, which is acceptable but not optimal.

A more optimal solution uses bit manipulation. Consider that for a number with alternating bits, shifting the number right by one bit and XORing it with the original number should produce a binary number with all bits set to 1. This is because XOR returns 1 for differing bits and 0 for equal bits. Once we get this XOR result, we can check if it is of the form 2^k - 1 by verifying that x & (x + 1) == 0. This property comes from the observation that numbers like 1, 11, 111, etc., in binary satisfy this identity.

Approach Time Complexity Space Complexity Notes
Brute Force O(log n) O(1) Iteratively compare each bit with the previous bit
Optimal O(log n) O(1) Use bit manipulation and XOR to check pattern in a single step

Algorithm Walkthrough

  1. Start with the input number n.
  2. Compute shifted = n >> 1. This moves all bits of n one position to the right.
  3. Compute xor_result = n ^ shifted. This XOR operation will produce a number where each bit is 1 if the original bits were different, which is exactly what alternating bits produce.
  4. To check whether xor_result is a sequence of all 1s, use the expression xor_result & (xor_result + 1). If the result is 0, then xor_result is of the form 2^k - 1, meaning n has alternating bits.
  5. Return true if the check passes, otherwise false.

Why it works: The algorithm relies on the property that XOR of consecutive bits in an alternating sequence produces all ones, and all ones in binary satisfy the identity x & (x + 1) == 0. This invariant guarantees correctness for all valid input numbers.

Python Solution

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        shifted = n >> 1
        xor_result = n ^ shifted
        return (xor_result & (xor_result + 1)) == 0

In this implementation, the first step shifts n by one to align consecutive bits for comparison. The XOR operation detects where bits differ, and the final check ensures all bits in xor_result are set, which indicates alternating bits. This method avoids iterating over each bit individually.

Go Solution

func hasAlternatingBits(n int) bool {
    shifted := n >> 1
    xorResult := n ^ shifted
    return (xorResult & (xorResult + 1)) == 0
}

The Go implementation mirrors Python’s approach. Bitwise operations are used directly on integers. There are no concerns with integer overflow within the 32-bit range of the problem constraints, and Go handles bitwise operations on int types efficiently.

Worked Examples

Example 1: n = 5 (binary 101)

Step Value
n 101
shifted 010
xor_result 111
xor_result & (xor_result + 1) 111 & 1000 = 0
Return true

Example 2: n = 7 (binary 111)

Step Value
n 111
shifted 011
xor_result 100
xor_result & (xor_result + 1) 100 & 101 = 100 != 0
Return false

Example 3: n = 11 (binary 1011)

Step Value
n 1011
shifted 0101
xor_result 1110
xor_result & (xor_result + 1) 1110 & 1111 = 1110 != 0
Return false

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Each bit is processed once in the XOR and shift operations; the number of bits is proportional to log n
Space O(1) Only a constant number of integer variables are used

The complexity is efficient for 32-bit integers, and the approach is scalable to larger numbers as well.

Test Cases

# test cases
assert Solution().hasAlternatingBits(5) == True  # 101
assert Solution().hasAlternatingBits(7) == False # 111
assert Solution().hasAlternatingBits(11) == False # 1011
assert Solution().hasAlternatingBits(1) == True  # single bit
assert Solution().hasAlternatingBits(10) == True # 1010
assert Solution().hasAlternatingBits(0b1010101) == True # 85, longer alternating
assert Solution().hasAlternatingBits(0b1111111) == False # all ones
assert Solution().hasAlternatingBits(0b100000) == True # 32, single one at high bit
Test Why
5 Standard alternating pattern
7 All bits the same
11 Non-alternating with mixture of ones and zeros
1 Single bit edge case
10 Alternating ending with zero
85 Longer alternating pattern
127 All ones, edge case
32 Single one at high position, alternating trivially

Edge Cases

One important edge case is n = 1. Since it has only one bit, it should return true. A naive implementation comparing consecutive bits might fail if it does not handle single-bit numbers properly. Our bitwise approach handles it naturally because the XOR of n with n >> 1 produces 1, and the final check (1 & 2) == 0 holds.

Another edge case is numbers with all ones in their binary representation, like n = 7 or n = 127. These numbers do not have alternating bits, and the XOR approach detects the pattern correctly, returning false because the XOR result is not all ones.

A third edge case is numbers where the alternating pattern ends with 0, such as n = 10 (binary 1010). Some iterative solutions might assume alternating sequences must start or end with 1. Our solution does not have this bias, since the XOR and bit check correctly handle both cases.