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 - 1Problem 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.
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.
Time Complexity: O(1), Space Complexity: O(1)
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.
Time Complexity: O(log N), where N is the value of the number. Space Complexity: O(1)
| 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) |
| 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. |
Binary Number with Alternating Bits | 3 Approaches | Detailed | Leetcode 693 | codestorywithMIK • codestorywithMIK • 4,501 views views
Watch 9 more video solutions →Practice Binary Number with Alternating Bits with our built-in code editor and test cases.
Practice on FleetCode