Binary Number with Alternating Bits

EASY

Description

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

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

Approaches

Checkout 3 different approaches to solve Binary Number with Alternating Bits. Click on different approaches to view the approach and algorithm in detail.

Convert to String and Iterate

This approach converts the integer into its binary string representation. Then, it iterates through the string to check if any two adjacent characters (bits) are the same. If it finds such a pair, the number does not have alternating bits. If the entire string is traversed without finding such a pair, the bits are alternating.

Algorithm

Convert the input integer n to its binary string representation using Integer.toBinaryString(n).
Loop through the binary string from the second character (index 1) to the end.
In each iteration, compare the current character s.charAt(i) with the previous character s.charAt(i-1).
If s.charAt(i) == s.charAt(i-1), it means two adjacent bits are the same. Return false immediately.
If the loop completes without returning, it means all adjacent bits were different. Return true.

This is the most straightforward approach. We first convert the number into a sequence of characters representing its bits and then perform a simple linear scan to check for the alternating property.

class Solution {
    public boolean hasAlternatingBits(int n) {
        String binaryString = Integer.toBinaryString(n);
        for (int i = 1; i < binaryString.length(); i++) {
            if (binaryString.charAt(i) == binaryString.charAt(i - 1)) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(log n). The number of bits in `n` is proportional to log₂(n). Converting the number to a string and iterating through it both take time proportional to the number of bits.Space Complexity: O(log n). We need to store the binary string representation of `n`, which requires space proportional to the number of bits.

Pros and Cons

Pros:

Simple to understand and implement.
Leverages built-in language features for number-to-string conversion.

Cons:

Less efficient in terms of both time and space compared to bit manipulation approaches.
Incurs overhead from string object creation and character access.

Code Solutions

Checking out 3 solutions in different languages for Binary Number with Alternating Bits. Click on different languages to view the code.

class Solution {
public
  boolean hasAlternatingBits(int n) {
    n ^= (n >> 1);
    return (n & (n + 1)) == 0;
  }
}

Video Solution

Watch the video walkthrough for Binary Number with Alternating Bits

Patterns:

Bit Manipulation