Binary Number with Alternating Bits

Difficulty: Easy | Acceptance: 69.90% | Paid: No Topics: Bit Manipulation

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

• Examples
• Constraints
• Approach 1: String Conversion
• Approach 2: Iterative Bit Manipulation
• Approach 3: XOR and Check

Examples

Example 1:

Input: n = 5
Output: true
Explanation: The binary representation of 5 is: 101

Example 2:

Input: n = 7
Output: false
Explanation: The binary representation of 7 is: 111.

Example 3:

Input: n = 11
Output: false
Explanation: The binary representation of 11 is: 1011.

Constraints

1 <= n <= 2³¹ - 1

Approach 1: String Conversion

Intuition Convert the integer to its binary string representation and iterate through the characters to check for any consecutive identical bits.

Steps

• Convert the integer n to a binary string.
• Iterate through the string from the first character to the second to last character.
• If any character is equal to the next character, return false.
• If the loop completes without finding duplicates, return true.

Complexity

• Time: O(log n) to convert and iterate through the bits.
• Space: O(log n) to store the binary string.
• Notes: Simple to implement but uses extra space proportional to the number of bits.

Approach 2: Iterative Bit Manipulation

Intuition Process the bits directly without converting to a string. Compare the last bit with the previous bit as we shift the number right.

Steps

• Store the last bit of n (using n & 1).
• Right shift n by 1.
• While n is greater than 0:
  • Get the current last bit of n.
  • If the current bit is equal to the previous bit, return false.
  • Update the previous bit to the current bit.
  • Right shift n by 1.
• Return true if the loop finishes.

Complexity

• Time: O(log n) to iterate through the bits.
• Space: O(1) constant extra space.
• Notes: More space-efficient than the string approach.

Approach 3: XOR and Check

Intuition If a number has alternating bits, shifting it right by 1 and XORing it with itself will result in a number with all bits set to 1. We can then verify if the result is of the form 2ᵏ - 1.

Steps

• Compute x = n ^ (n >> 1).
• Check if x & (x + 1) equals 0. This property holds true only if x consists of all 1s (e.g., 111…1).

Complexity

• Time: O(1) operations are constant time for fixed-size integers.
• Space: O(1) constant extra space.
• Notes: The most optimal solution with clever bit manipulation tricks.