Problem statement

https://leetcode.com/problems/binary-number-with-alternating-bits/

Solution

There is starighforward O(32) solution, where we just check bits, either in string, or in number directly. There is also O(1) complexity solution, where we use structure of number: if we have 1010101 and we shift it two bits 10101 and evaluate xor, we get 1000000, and all we need to check now is it is power of two, for this we have x&(x-1) trick.

Complexity

Time and space complexity is O(1).

Code

class Solution:
    def hasAlternatingBits(self, n):
        n ^= n >> 2
        return not (n & (n - 1))