Jobs

Interviews

Discussions

Binary Number with Alternating Bits

Easy

Asked by:

12 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Binary Number with Alternating Bits

Easy

Asked by:

12 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the binary number can have? Specifically, what is the maximum possible integer value?
Is the input guaranteed to be a non-negative integer?
Should I return `true` if the input is 0?
By 'alternating bits,' do you mean that adjacent bits must always be different (e.g., 101010 or 010101) and there cannot be consecutive identical bits?
Are leading zeros allowed in the binary representation of the number? If so, should they be considered when determining the alternating pattern?

Brute Force Solution

Approach

The brute force approach checks every single digit in the number one at a time. We compare each digit with the one right before it to see if they alternate.

Here's how the algorithm would work step-by-step:

Start by looking at the second digit of the number.
Check if this digit is different from the digit right before it.
If they are the same, the number does not have alternating bits, and we are done.
If they are different, move on to the next digit and repeat the checking process.
Keep doing this until we reach the end of the number.
If we get to the end and all the digits have alternated correctly, then the number has alternating bits.

Code Implementation

def has_alternating_bits_brute_force(number):
    binary_representation = bin(number)[2:]
    number_of_bits = len(binary_representation)

    # Need at least 2 bits to have alternating bits
    if number_of_bits < 2:
        return True

    for index in range(1, number_of_bits):
        # Compare current bit to the previous bit
        if binary_representation[index] == binary_representation[index - 1]:

            # If the bits are equal, it's not alternating
            return False

    return True

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iterates through the bits of the input number n. The number of bits in a binary representation of a number is proportional to the logarithm base 2 of that number (log₂ n). The algorithm performs a constant amount of work for each bit. Therefore, the time complexity is proportional to the number of bits, resulting in a time complexity of O(log n).

Space Complexity

O(1) – The provided algorithm iterates through the digits of the binary number. It only requires a constant amount of extra space to store a few variables during the digit comparison. These variables hold the current and previous digits during the check. The number of digits, N, which is the size of the input, does not affect the amount of extra memory used. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks us to check if a number's binary representation has alternating bits (0101 or 1010). The clever approach involves recognizing a pattern in the binary number itself to efficiently confirm this alternation, avoiding complex bit-by-bit comparisons.

Here's how the algorithm would work step-by-step:

First, take the given number and shift it to the right by one position.
Next, perform a bitwise XOR operation between the original number and the shifted number.
After that, add one to the result of the XOR operation.
Finally, check if the new result is a power of two (meaning it only has one '1' bit in its binary representation). If it is, the original number had alternating bits.

Code Implementation

def has_alternating_bits(number):
    shifted_number = number >> 1

    # XOR to highlight differences between adjacent bits.
    xor_result = number ^ shifted_number

    added_result = xor_result + 1

    # Power of 2 check confirms alternating pattern.
    return (added_result & (added_result - 1)) == 0

Big(O) Analysis

Time Complexity

O(1) – The algorithm involves a fixed number of bitwise operations: a right shift, an XOR operation, an addition, and a check for power of two. These operations are independent of the size of the input number 'n' (number of bits). Determining if a number is a power of two also involves a bitwise AND, which is O(1). Therefore, the overall time complexity is constant, or O(1).

Space Complexity

O(1) – The algorithm performs bitwise operations and stores the results in place. It utilizes a few integer variables to hold the shifted number and the result of the XOR operation. No additional data structures that scale with the input number are used, therefore the auxiliary space is constant and independent of the input.

Edge Cases

Case	How to Handle
Input is zero (0)	Zero is not considered to have alternating bits, so return false.
Input is one (1)	One is considered to have alternating bits, so return true.
Large integer inputs close to the maximum integer value.	Ensure the bitwise operations or string conversions used in the solution do not cause integer overflow leading to incorrect results.
Integer with all 1s (e.g., 2^n - 1) as input	This should return false, because all bits are 1s, and it doesn't have alternating bits.
Powers of 2 as inputs (e.g., 2, 4, 8, 16...)	Check for this explicitly as they contain only one set bit, therefore do not have alternating bits.
Negative input.	The problem statement does not specify the behavior for negative numbers, clarify that negative numbers are invalid inputs and should be rejected.
Integer with alternating bits starting with 0 (e.g., 42 (101010))	The algorithm must correctly identify alternating patterns regardless of whether they start with 0 or 1.
Integer with repeating sequences of bits like 110011 or 100100	Ensure the algorithm does not incorrectly identify these as alternating since alternating needs to be between adjacent bits.

Input is zero (0)

How to Handle:

Zero is not considered to have alternating bits, so return false.

Input is one (1)

How to Handle:

One is considered to have alternating bits, so return true.

Large integer inputs close to the maximum integer value.

How to Handle:

Ensure the bitwise operations or string conversions used in the solution do not cause integer overflow leading to incorrect results.

Integer with all 1s (e.g., 2^n - 1) as input

How to Handle:

This should return false, because all bits are 1s, and it doesn't have alternating bits.

Powers of 2 as inputs (e.g., 2, 4, 8, 16...)

How to Handle:

Check for this explicitly as they contain only one set bit, therefore do not have alternating bits.

Negative input.

How to Handle:

The problem statement does not specify the behavior for negative numbers, clarify that negative numbers are invalid inputs and should be rejected.

Integer with alternating bits starting with 0 (e.g., 42 (101010))

How to Handle:

The algorithm must correctly identify alternating patterns regardless of whether they start with 0 or 1.

Integer with repeating sequences of bits like 110011 or 100100

How to Handle:

Ensure the algorithm does not incorrectly identify these as alternating since alternating needs to be between adjacent bits.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values that the binary number can have? Specifically, what is the maximum possible integer value?
Is the input guaranteed to be a non-negative integer?
Should I return `true` if the input is 0?
By 'alternating bits,' do you mean that adjacent bits must always be different (e.g., 101010 or 010101) and there cannot be consecutive identical bits?
Are leading zeros allowed in the binary representation of the number? If so, should they be considered when determining the alternating pattern?

Brute Force Solution

Approach

The brute force approach checks every single digit in the number one at a time. We compare each digit with the one right before it to see if they alternate.

Here's how the algorithm would work step-by-step:

Start by looking at the second digit of the number.
Check if this digit is different from the digit right before it.
If they are the same, the number does not have alternating bits, and we are done.
If they are different, move on to the next digit and repeat the checking process.
Keep doing this until we reach the end of the number.
If we get to the end and all the digits have alternated correctly, then the number has alternating bits.

Code Implementation

def has_alternating_bits_brute_force(number):
    binary_representation = bin(number)[2:]
    number_of_bits = len(binary_representation)

    # Need at least 2 bits to have alternating bits
    if number_of_bits < 2:
        return True

    for index in range(1, number_of_bits):
        # Compare current bit to the previous bit
        if binary_representation[index] == binary_representation[index - 1]:

            # If the bits are equal, it's not alternating
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, take the given number and shift it to the right by one position.
Next, perform a bitwise XOR operation between the original number and the shifted number.
After that, add one to the result of the XOR operation.
Finally, check if the new result is a power of two (meaning it only has one '1' bit in its binary representation). If it is, the original number had alternating bits.

Code Implementation

def has_alternating_bits(number):
    shifted_number = number >> 1

    # XOR to highlight differences between adjacent bits.
    xor_result = number ^ shifted_number

    added_result = xor_result + 1

    # Power of 2 check confirms alternating pattern.
    return (added_result & (added_result - 1)) == 0

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero (0)	Zero is not considered to have alternating bits, so return false.
Input is one (1)	One is considered to have alternating bits, so return true.
Large integer inputs close to the maximum integer value.	Ensure the bitwise operations or string conversions used in the solution do not cause integer overflow leading to incorrect results.
Integer with all 1s (e.g., 2^n - 1) as input	This should return false, because all bits are 1s, and it doesn't have alternating bits.
Powers of 2 as inputs (e.g., 2, 4, 8, 16...)	Check for this explicitly as they contain only one set bit, therefore do not have alternating bits.
Negative input.	The problem statement does not specify the behavior for negative numbers, clarify that negative numbers are invalid inputs and should be rejected.
Integer with alternating bits starting with 0 (e.g., 42 (101010))	The algorithm must correctly identify alternating patterns regardless of whether they start with 0 or 1.
Integer with repeating sequences of bits like 110011 or 100100	Ensure the algorithm does not incorrectly identify these as alternating since alternating needs to be between adjacent bits.

Input is zero (0)

How to Handle:

Zero is not considered to have alternating bits, so return false.

Input is one (1)

How to Handle:

One is considered to have alternating bits, so return true.

Large integer inputs close to the maximum integer value.

How to Handle:

Ensure the bitwise operations or string conversions used in the solution do not cause integer overflow leading to incorrect results.

Integer with all 1s (e.g., 2^n - 1) as input

How to Handle:

This should return false, because all bits are 1s, and it doesn't have alternating bits.

Powers of 2 as inputs (e.g., 2, 4, 8, 16...)

How to Handle:

Check for this explicitly as they contain only one set bit, therefore do not have alternating bits.

Negative input.

How to Handle:

The problem statement does not specify the behavior for negative numbers, clarify that negative numbers are invalid inputs and should be rejected.

Integer with alternating bits starting with 0 (e.g., 42 (101010))

How to Handle:

The algorithm must correctly identify alternating patterns regardless of whether they start with 0 or 1.

Integer with repeating sequences of bits like 110011 or 100100

How to Handle:

Ensure the algorithm does not incorrectly identify these as alternating since alternating needs to be between adjacent bits.