How do you solve Binary Number with Alternating Bits on LeetCode?

Binary Number with Alternating Bits (LeetCode #693) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Bit manipulation can simplify the problem significantly.

What is the brute force solution for Binary Number with Alternating Bits?

The brute force approach for Binary Number with Alternating Bits is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves converting the integer to its binary representation and checking each pair of adjacent bits to see if they differ. This is straightforward but can be inefficient for larger numbers. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Binary Number with Alternating Bits?

Binary Number with Alternating Bits uses the following concepts: Bit Manipulation. The recommended patterns to study are: Bit Manipulation, Greedy.

What are the interview tips for Binary Number with Alternating Bits?

Explain your thought process clearly while coding. Discuss potential edge cases before jumping into the code. Practice bit manipulation problems to build confidence.

What are common mistakes when solving Binary Number with Alternating Bits?

Converting to binary unnecessarily when bit manipulation can be used. Not considering edge cases like the smallest numbers.

#693

Binary Number with Alternating Bits

Easy

Bit ManipulationBit ManipulationGreedy

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages bit manipulation to check for alternating bits without converting to a binary string. This is more efficient as it directly uses the properties of binary numbers.

⚙️

Algorithm

3 steps

1Step 1: Create a variable 'prev' initialized to -1 to store the previous bit.
2Step 2: Use a loop to right-shift the number until it becomes 0.
3Step 3: In each iteration, check if the last bit (n & 1) is the same as 'prev'. If yes, return false; otherwise, update 'prev' and right-shift n.

solution.py11 lines

1# Full working Python code
2
3def hasAlternatingBits(n):
4    prev = -1
5    while n > 0:
6        current = n & 1  # Get the last bit
7        if current == prev:
8            return False
9        prev = current
10        n >>= 1  # Right shift n
11    return True

ℹ

Complexity note: The time complexity is O(n) because we process each bit of the number once. The space complexity is O(1) as we are only using a fixed amount of extra space.

1Bit manipulation can simplify the problem significantly.
2Understanding binary representation helps in optimizing solutions.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.