Binary Number with Alternating Bits

Problem Statement

The task is to determine if a given positive integer has alternating bits in its binary representation. This means that when we look at the sequence of bits for the number, each bit should be different from the one next to it. For instance, the number 5, which has a binary representation of '101', fulfills this condition, hence the output should be true. In contrast, a number like 7, represented as '111' in binary, does not meet the criterion since all the bits are the same and adjacent bits do not alternate.

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 <= 231 - 1

Approach and Intuition

The problem of checking for alternating bits in the binary representation of an integer can be approached in several intuitive ways:

1. Convert the integer to its binary representation and then traverse through it to check adjacent bits.
2. Utilize bitwise operations to avoid explicitly creating the binary string and directly determine the alternating pattern.

Below is the intuitive explanation based on the examples given:

• Example 1:

  • For n = 5, the binary form is 101.
  • Here, you can observe each bit differs from its neighbor: 1 differs from 0 and 0 from the next 1.
  • Using a simple loop can easily check these criteria by comparing each bit with the next one.

• Example 2:

  • For n = 7, the binary form is 111.
  • In this case, there’s no alternation since all bits are the same. This is directly visible and will fail the alternating bit check immediately at the second bit.

• Example 3:

  • For n = 11, represented as 1011, you'll see that while it starts with an alternating pattern (1 to 0 to 1), it fails at the last two digits where 1 is followed by another 1.

From this observation and direct checks from the examples provided, a simple method could be to:

1. Check each bit of the number using bitwise operations or string manipulation.
2. Compare it to its preceding bit to ensure they alternate.
3. Return false at the first instance of finding two consecutive similar bits, otherwise, after the check, return true if all bits alternated cleanly.

The constraints 1 <= n <= 231 - 1 ensure that the number is always positive, allowing simplified handling of edge cases, as numbers will always have a valid binary representation.

Solutions

class Solution {
    public boolean checkBitsAlternation(int number) {
        int currentBit = number % 2;
        number /= 2;
        while (number > 0) {
            if (currentBit == number % 2) return false;
            currentBit = number % 2;
            number /= 2;
        }
        return true;
    }
}