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.
Example 4:
Input: n = 2
Output: true
Explanation: The binary representation of 10 is: 1010.
Example 5:
Input: n = 3
Output: false
Constraints:
1 <= n <= 231 - 1
public class Solution {
public bool HasAlternatingBits(int n) {
int? prev = null;
for(int i=0;i<32 && n!=0;i++){
if(prev==null){
prev = (n&1);
}
else{
if(prev == (n&1)){
return false;
}
prev = (n&1);
}
n=n>>1;
}
return true;
}
}
Time Complexity: O(logn) which corresponds to the count of binary bits.
Space Complexity: O(1)