Sponsored
Sponsored
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 <stdbool.h>
2
3bool hasAlternatingBits(int n) {
4 int xor = n ^ (n >> 1);
5 return (xor & (xor + 1)) == 0;
6}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.
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 public bool HasAlternatingBits(int n) {
while (n > 0) {
int last = n % 2;
n = n >> 1;
if (last == (n % 2)) return false;
}
return true;
}
}The iterative approach in C# checks adjacent bits by evaluating the last lowest binary digits and then progressively reducing the integer by logical shifts.