Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.
Example 1:
Input: 5 Output: True Explanation: The binary representation of 5 is: 101
Example 2:
Input: 7 Output: False Explanation: The binary representation of 7 is: 111.
Example 3:
Input: 11 Output: False Explanation: The binary representation of 11 is: 1011.
Example 4:
Input: 10 Output: True Explanation: The binary representation of 10 is: 1010.
Intuition and Algorithm
Let's convert the given number into a string of binary digits. Then, we should simply check that no two adjacent digits are the same.
Complexity Analysis
Time Complexity: . For arbitrary inputs, we do work, where is the number of bits in n
. However, .
Space complexity: , or alternatively .
Intuition and Algorithm
We can get the last bit and the rest of the bits via n % 2
and n // 2
operations. Let's remember cur
, the last bit of n
. If the last bit ever equals the last bit of the remaining, then two adjacent bits have the same value, and the answer is False
. Otherwise, the answer is True
.
Also note that instead of n % 2
and n // 2
, we could have used operators n & 1
and n >>= 1
instead.
Complexity Analysis
Time Complexity: . For arbitrary inputs, we do work, where is the number of bits in n
. However, .
Space complexity: .
Analysis written by: @awice