Given a positive integer n. The task is to check whether this integer has an alternate pattern of 0 and 1 in its binary representation or not.
NOTE: Return 1 if the integer has alternate 0 and 1 in its binary representation else return 0. 
Example 1:
Input: n = 12
Output: 0 
Explanation: n = 12 = "1100" 
Hence there is no alternate pattern.
Example 2:
Input: n = 10
Output: 1
Explanation: n = 10 = "1010".
Hence n has an alternate pattern.
Your Task:  
You dont need to read input or print anything. Complete the function bitsAreInAltOrder() which takes n as input parameter and returns 1 if the integer has alternate 0 and 1 in its binary representation else return 0.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
1<= n <=10^{15}

Difficulty: EASY
Tags: Bit manipulation

Data structures
Skill types: Bit manipulation

Data structures
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3
class Solution:
    def bitsAreInAltOrder (self, n):
        # code here 

Solutions:
class Solution:

	def bitsAreInAltOrder(self, n):
		s = bin(n)
		for i in range(3, len(s)):
			if s[i] == s[i - 1]:
				return 0
		return 1


class Solution:

	def bitsAreInAltOrder(self, n):
		n = n ^ n >> 1
		return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		n = bin(n)[2:]
		s1 = n.split('10')
		s2 = n.split('01')
		if all((i == '' for i in s1)):
			return 1
		elif all((i == '' for i in s2)):
			return 1
		else:
			return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		num = bin(n)[2:]
		for i in range(len(num) - 1):
			if num[i] == num[i + 1]:
				return 0
		return 1


class Solution:

	def bitsAreInAltOrder(self, n):
		b = bin(n).replace('0b', '')
		even = set()
		odd = set()
		for (i, v) in enumerate(b):
			if i % 2 == 0:
				even.add(v)
			else:
				odd.add(v)
		return 1 if len(even) == 1 and len(odd) == 1 else 0


class Solution:

	def bitsAreInAltOrder(self, n):
		i = 1
		cnt = 0
		while i < n:
			i *= 2
			cnt += 1
		j = 0
		if n % 2 == 0:
			num = 2
		else:
			num = 1
		cnt -= 2
		while j < cnt:
			num = num | num << 2
			j += 2
		if num == n:
			return 1
		else:
			return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		num = n ^ n >> 1
		if num & num + 1 == 0:
			return 1
		return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		arr = bin(n)
		ele = arr[0]
		i = 1
		while i < len(arr):
			if arr[i] == ele:
				return 0
			ele = arr[i]
			i += 1
		return 1


class Solution:

	def bitsAreInAltOrder(self, n):
		string = bin(n)[2:]
		length = len(string)
		for i in range(1, length, 2):
			if string[i] == string[i - 1]:
				return 0
			if i < length - 1 and string[i] == string[i + 1]:
				return 0
		return 1


class Solution:

	def bitsAreInAltOrder(self, n):
		res = bin(n).replace('0b', '')
		l = list(res)
		for i in range(len(l) - 1):
			if l[i] == l[i + 1]:
				return 0
		return 1


class Solution:

	def bitsAreInAltOrder(self, n):
		i = 1
		n = bin(n)[2:]
		for j in n:
			if j != i:
				return 0
			elif i == 1:
				i = 0
			else:
				i = 1
		return 1


class Solution:

	def bitsAreInAltOrder(self, n):
		n = n ^ n >> 1
		if n & n + 1 == 0:
			return 1
		else:
			return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		ans = n ^ n >> 1
		if ans ^ ans + 1 == 0:
			return 1
		return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		s = bin(n)
		s = s[2:]
		d = len(s)
		f = 0
		for i in range(d):
			if i % 2 == 0 and s[i] != '1':
				return 0
			if i % 2 == 1 and s[i] != '0':
				return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.bitsAreInAltOrder(n))


class Solution:

	def bitsAreInAltOrder(self, n):
		n = bin(n)[2:]
		for i in range(1, len(n), 2):
			if n[i] != 0 and n[i + 1] != 1:
				return 0
			elif n[i] != 1 and n[i + 1] != 0:
				return 0
			else:
				return 1


class Solution:

	def bitsAreInAltOrder(self, n):
		ones = n ^ n >> 1
		if not ones:
			return 0
		if ones & ones + 1:
			return 0
		return 1


import math

class Solution:

	def bitsAreInAltOrder(self, n):
		numberOfBits = self.getLength(n)
		return int(n ^ n >> 1 == (1 << numberOfBits) - 1)

	def getLength(self, n):
		return int(math.log2(n)) + 1


import math

class Solution:

	def bitsAreInAltOrder(self, n):
		bits = math.floor(math.log(n, 2)) + 1
		if n ^ n >> 1 == (1 << bits) - 1:
			return 1
		return 0


import math

class Solution:

	def bitsAreInAltOrder(self, n):
		bits = math.floor(math.log(n, 2)) + 1
		bits = math.ceil(bits / 2)
		if n & 1 == 1:
			a = 1
		else:
			a = 2
		num = int((4 ** bits - 1) * a / 3)
		if n == num:
			return 1
		return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		st = bin(n)[2:]
		if '11' in st:
			return 0
		elif '00' in st:
			return 0
		else:
			return 1


from math import log2

class Solution:

	def bitsAreInAltOrder(self, n):
		l = 2 ** (int(log2(n)) + 1) - 1
		if n ^ n >> 1 == l:
			return 1
		return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		s = len(bin(n)) - 2
		if n ^ n >> 1 == 2 ** s + ~0:
			return 1
		else:
			return 0


class Solution:

	def bitsAreInAltOrder(self, n):
		a = n ^ n >> 1
		if a & a + 1 == 0:
			return 1
		return 0