693. Binary Number with Alternating Bits
1. Description
Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
2. Example
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 = 10
Output: true
Explanation: The binary representation of 10 is: 1010.
Example 5
Input: n = 3
Output: false
3. Constraints
- 1 <= n <= 2$^{31}$ - 1
4. Solutions
Bit Manipulation
Time complexity: O(1)
Space complexity: O(1)
class Solution
{
public:
// bool hasAlternatingBits(int n)
bool hasAlternatingBits(int num)
{
// pass leading zero
int leftMove = 31;
while((num & (1 << leftMove)) == 0) leftMove--;
int lastOnePosition = INT_MAX, lastZeroPosition = INT_MAX;
for(; leftMove >= 0; leftMove--)
{
if(num & (1 << leftMove))
{
if(lastOnePosition - leftMove == 1) return false;
lastOnePosition = leftMove;
}
else
{
if(lastZeroPosition - leftMove == 1) return false;
lastZeroPosition = leftMove;
}
}
return true;
}
};