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 - 1The goal of #693 Binary Number with Alternating Bits is to determine whether the binary representation of a given integer alternates between 0 and 1 at every position. This is a classic bit manipulation problem that tests your understanding of binary operations.
A straightforward approach is to repeatedly compare the last two bits of the number. Extract the last bit using n & 1, shift the number right using n >> 1, and ensure that the current bit differs from the previous one. If two adjacent bits match, the number does not have alternating bits.
A more elegant bit manipulation trick uses XOR. If you compute x = n ^ (n >> 1), an integer with alternating bits produces a sequence of all 1s. You can then verify this property by checking whether x & (x + 1) == 0. Both approaches run in constant time because integers have a fixed number of bits.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit-by-bit comparison using shifting | O(1) | O(1) |
| XOR trick with all-ones validation | O(1) | O(1) |
NeetCode
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.
Time Complexity: O(1), Space Complexity: O(1)
1#include <iostream>
2
3bool hasAlternatingBits(int n) {
4 int xor_result = n ^ (n >> 1);
5 return (xor_result & (xor_result + 1)) == 0;
6}Using XOR operation and shifting the number, it checks for the condition that results in all 1s for alternating bits. The condition is simple: (xor_result & (xor_result + 1)) == 0.
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.
Time Complexity: O(log N), where N is the value of the number. Space Complexity: O(1)
1
bool hasAlternatingBits(int n) {
while(n > 0) {
int last = n % 2;
n = n >> 1;
if(last == (n % 2)) return false;
}
return true;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of bit manipulation problems like Binary Number with Alternating Bits are common in technical interviews, including FAANG-style interviews. They are used to evaluate a candidate’s understanding of binary operations and low-level optimization.
No special data structure is required for this problem. It is best solved using bit manipulation operations directly on the integer, which keeps both time and space usage minimal.
The optimal approach uses bit manipulation with XOR. Compute x = n ^ (n >> 1); if the number has alternating bits, x becomes a sequence of all 1s. You can then check this using the condition x & (x + 1) == 0.
Yes, you could convert the number to a binary string and check whether adjacent characters differ. However, this approach is less efficient and less elegant than using direct bit operations.
The solution uses a loop to check paired bits from right to left, comparing them to determine if they are alternating.