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)
1public class Solution {
2 public bool HasAlternatingBits(int n) {
3 int xor = n ^ (n >> 1);
4 return (xor & (xor + 1)) == 0;
5 }
6}The XOR result produces a sequence of 1s if the bits of n alternate. We confirm this by checking that all bits in the XOR result can perfectly be incremented by 1 and turning into the next number entirely composed of 0s.
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)
1This strategy uses modulus to check alternating nature by analyzing bits starting from the least significant ones and effectively shifting.