Binary Number with Alternating Bits - Solution & Explanation
Problem Statement
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 <= 231 - 1
Approach Overview
Problem Overview: Given a positive integer n, determine whether its binary representation contains alternating bits. That means every adjacent bit must differ, such as 101010 or 10. If any two neighboring bits are the same (like 110 or 1001), the number does not satisfy the condition.
Approach 1: Observation and Iterative Check (Time: O(log n), Space: O(1))
The straightforward solution inspects bits one by one from right to left. Extract the last bit using n & 1, then shift the number right using n >> 1. Track the previous bit and compare it with the current bit during each iteration. If two consecutive bits match, the pattern breaks and you return false.
This works because each right shift removes the least significant bit, letting you compare neighbors sequentially. The loop runs once for every bit in the number, which is O(log n) since the number of bits grows logarithmically with the value of n. Space remains O(1) because only a few variables are used.
This approach is easy to reason about and shows clear understanding of bit manipulation. It is often the first solution candidates write during interviews.
Approach 2: Bitwise Comparison Trick (Time: O(1), Space: O(1))
A more elegant approach relies on a useful property of alternating bit patterns. If you XOR a number with itself shifted right by one (x = n ^ (n >> 1)), the result becomes a sequence of all 1 bits when the original number had perfectly alternating bits. For example, 1010 ^ 0101 = 1111.
Once you obtain x, check whether it consists only of consecutive 1s. A number with all 1s has the property x & (x + 1) == 0. This works because adding 1 flips the entire run of 1s and introduces a carry into a new bit. If the AND operation returns zero, the pattern is valid.
This method compresses the entire validation into a couple of bit manipulation operations and avoids looping through individual bits. Runtime is effectively O(1) for fixed-width integers, with O(1) space.
Recommended for interviews: Start with the iterative bit check because it clearly demonstrates understanding of binary representation and shifting. After that, mention the XOR trick as an optimization. Interviewers typically expect the n ^ (n >> 1) insight since it shows strong familiarity with bit patterns and low-level operations.
Approach 1: Bitwise Comparison Approach
In this approach, we will use bitwise operations to compare each bit with its adjacent one. The key is to repeatedly XOR the number with itself shifted one position to the right, which will result in a number with all bits set to 1 if the original number has alternating bits. Such a number should satisfy (n & (n + 1)) == 0.
The function calculates the XOR of the number with itself shifted one bit to the right. If the number has alternating bits, the result will be all 1s in binary, satisfying the condition that XOR & (XOR + 1) equals zero.
Complexity
Time Complexity: O(1), Space Complexity: O(1)
Approach 2: Observation and Iterative Check
This approach involves checking each bit pair iteratively. We will repeatedly check if the last two bits are the same or different by analyzing the least significant bits and shifting the number to the right iteratively.
This implementation analyzes the last two bits of the number by checking the modulus and right-shifting iteratively. It ensures they are different, ensuring the bits alternate.
Complexity
Time Complexity: O(log N), where N is the value of the number. Space Complexity: O(1)
Approach 3: Simulation
We cyclically right-shift n until it becomes 0, checking whether the binary bits of n appear alternately. If during the loop we find that 0 and 1 do not appear alternately, we directly return false. Otherwise, when the loop ends, we return true.
The time complexity is O(log n), and the space complexity is O(1).
Approach 4: Bit Manipulation
Assuming 01 appears alternately, we can convert all trailing bits to 1 through misaligned XOR. Adding 1 gives us a power of 2, which is a number n (where n has only one bit that is 1). Then, using n \& (n + 1) can eliminate the last 1 bit.
At this point, check if it equals 0. If so, the assumption holds, and it is an alternating 01 sequence.
The time complexity is O(1), and the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Bitwise Comparison Approach | Time Complexity: O(1), Space Complexity: O(1) |
| Observation and Iterative Check | Time Complexity: O(log N), where N is the value of the number. Space Complexity: O(1) |
| Simulation | — |
| Bit Manipulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Observation and Iterative Bit Check | O(log n) | O(1) | Best when explaining logic step‑by‑step in interviews or when demonstrating understanding of binary traversal. |
| Bitwise XOR Comparison Trick | O(1) | O(1) | Preferred optimized solution using bit manipulation properties and constant-time checks. |
Video Solution
Binary Number with Alternating Bits | 3 Approaches | Detailed | Leetcode 693 | codestorywithMIK • codestorywithMIK • 4,662 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Number with Alternating Bits easy or hard?
Binary Number with Alternating Bits Python/Java solution
How to solve Binary Number with Alternating Bits in O(1)?
What is the best approach for Binary Number with Alternating Bits?
Is Binary Number with Alternating Bits asked at Google/Amazon/Meta?
What data structure is used in Binary Number with Alternating Bits?
What is the time complexity of Binary Number with Alternating Bits?
Ready to solve this problem?
Practice Binary Number with Alternating Bits with our built-in code editor and test cases.
Practice on FleetCode