Approach #1: Convert to String [Accepted]
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 .
Approach #2: Divide By Two [Accepted]
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