Given a number n, the task is to find all 1 to n bit numbers with no consecutive 1's in their binary representation. 
 
Example 1:
Input: n = 3
Output: 1 2 4 5
Explanation: All numbers upto 2 bit are:
1 - 1
2 - 10
3 - 11
4 - 100
5 - 101
6 - 110
7 - 111
Here 3, 6 and 7 have consecutive 1's in their 
binary representation. 
Example 2:
Input: n = 2
Output: 1 2 
Explanation: All numbers upto 2 bit are:
1 - 1
2 - 10
3 - 11
Here 3 has consecutive 1's in it's
binary representation.
 
Your Task:
You don't need to read or print anything.Your task is to complete the function numberWithNoConsecutiveOnes() which takes n as input parameter and returns a list of numbers in increasing order which do not contains 1's in their binary reperesentation.
 
Expected Time Complexity: O(2^{n})
Expected Space Complexity: O(n)
 
Constraints:
1 <= n <= 20

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
	def numberWithNoConsecutiveOnes(self, n):
		# Code here

Solutions:
class Solution:

	def solve(self, k, n, curr):
		if k == n:
			num = 0
			for i in range(len(curr)):
				num = num * 2 + int(curr[i])
			if num != 0:
				self.ans.append(num)
			return
		curr.append('0')
		self.solve(k + 1, n, curr)
		curr.pop()
		if len(curr) == 0 or curr[-1] == '0':
			curr.append('1')
			self.solve(k + 1, n, curr)
			curr.pop()

	def numberWithNoConsecutiveOnes(self, n):
		self.ans = []
		self.solve(0, n, [])
		return self.ans


from bisect import bisect_left
arr = [1]

class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		limit = 2 ** n
		item = arr[-1] + 1
		while arr[-1] < limit:
			num = bin(item)[2:]
			if '11' not in num:
				arr.append(item)
			item += 1
		return arr[:bisect_left(arr, limit)]


from bisect import bisect_left
arr = [1]

class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		item = arr[-1] + 1
		while arr[-1] < 2 ** n:
			num = bin(item)[2:]
			flag = True
			for i in range(len(num) - 1):
				if num[i:i + 2] == '11':
					flag = False
					break
			if flag:
				arr.append(item)
			item += 1
		return arr[:bisect_left(arr, 2 ** n)]


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		kk = []
		kk.append('1')
		k = 2 ** n - 1
		for i in range(2, k):
			m = bin(i)
			mm = str(m)
			if '11' not in mm:
				kk.append(i)
		return kk


import math

class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		lim = int(math.pow(2, n))
		res = []
		for i in range(1, lim):
			(di, f) = (i, 1)
			while i != 0:
				if i % 2 != 0 and (i >> 1) % 2 != 0:
					f = 0
					break
				i = i >> 1
			if f:
				res.append(di)
		return res


import math

class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		l = []
		k = int(math.pow(2, n))
		for i in range(1, k):
			if i & i << 1 == 0:
				l.append(i)
		return sorted(l)


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		l = []
		a = 1
		while len(bin(a)[2:]) <= n:
			if '11' not in bin(a)[2:]:
				l.append(a)
			a += 1
		return l


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		bit_numbers = 2 ** n - 1
		listt = []
		listt.append('1')
		for i in range(2, bit_numbers):
			Binary_representation = bin(i)
			Binary_representation_string = str(Binary_representation)
			if '11' not in Binary_representation_string:
				listt.append(i)
		return listt


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		d = 2 ** n
		l = []
		s = {}
		for i in range(1, d):
			if i not in s:
				l.append(i)
				if i % 2:
					s[i * 2 + 1] = 1
			else:
				e = i * 2
				s[e] = 1
				s[e + 1] = 1
		return l


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		a = []
		for i in range(1, 2 ** n):
			m = i & i >> 1
			if m == 0:
				a.append(i)
		return a
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.numberWithNoConsecutiveOnes(n)
		for _ in ans:
			print(_, end=' ')
		print()


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		res = ['1']
		k = 2 ** n - 1
		for i in range(2, k):
			b = str(bin(i))
			if '11' not in b:
				res.append(i)
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.numberWithNoConsecutiveOnes(n)
		for _ in ans:
			print(_, end=' ')
		print()


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		ans = []
		self.genNumbers(n, ans, 0, 0, '')
		ans.remove(0)
		return sorted(list(ans))

	def genNumbers(self, n, ans, cur_len, cur_ans, cur_str):
		if cur_len == n:
			ans.append(cur_ans)
			return
		if not cur_str or cur_str[0 - 1] == '0':
			self.genNumbers(n, ans, cur_len + 1, cur_ans * 2 + 1, cur_str + '1')
		self.genNumbers(n, ans, cur_len + 1, cur_ans * 2 + 0, cur_str + '0')
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.numberWithNoConsecutiveOnes(n)
		for _ in ans:
			print(_, end=' ')
		print()


def decimalToBinary(n):
	return bin(n).replace('0b', '')

class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		ans = []
		for i in range(1, 2 ** n):
			k = decimalToBinary(i)
			if '11' not in k:
				ans.append(i)
		return ans


class Solution:

	def numberWithNoConsecutiveOnes(self, n):

		def check(num):
			prev = num % 2
			num //= 2
			while num > 0:
				x = num % 2
				if prev == 1 and prev == x:
					return False
				prev = x
				num //= 2
			return True
		r = 2 ** n - 1
		x = 2
		l = [1]
		while x <= r:
			if check(x):
				l.append(x)
			x += 1
		return l


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		l = []
		for i in range(1, 2 ** n):
			if i & i << 1 == 0:
				l.append(i)
		return l


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		a = [1]
		for k in range(2, 2 ** n - 1):
			s = bin(k)[2:]
			if '11' not in s:
				a.append(k)
		return a


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		ans = []
		k = 2 ** n
		for i in range(1, k):
			s = bin(i)[2:]
			if '11' in s:
				continue
			ans.append(i)
		return ans


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		out = []
		for i in range(1, 2 ** n):
			if '11' not in bin(i):
				out.append(i)
		return out


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		s = []
		for i in range(1, 2 ** n):
			j = str(bin(i).replace('0b', ''))
			if j.count('11') == 0:
				s.append(i)
		return s


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		l = []
		y = pow(2, n)
		for i in range(1, y):
			x = bin(i)
			x = x.replace('0b', '')
			if '11' not in x:
				l.append(x)
		for i in range(len(l)):
			l[i] = int(l[i], 2)
		return l


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		l = []
		i = 1
		while True:
			t = bin(i)
			t = t[2:]
			if len(t) <= n:
				l.append(t)
			if len(t) > n:
				break
			i += 1
		res = []
		for i in l:
			if '11' not in i:
				res.append(int(i, 2))
		return res


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		arr = []
		for i in range(2 ** n + 1, 2 ** (n + 1)):
			a = bin(i)[3:]
			if '11' not in a:
				arr.append(int(a, 2))
		return arr


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		ans = []
		x = 2 ** n
		count = 0
		for i in range(1, x):
			b = bin(i)
			if '11' in b:
				count += 1
			else:
				ans.append(i)
		return ans


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		result = []
		for num in range(1, 2 ** n):
			bn = bin(num)[2:]
			if self.helper(bn):
				result.append(num)
		return result

	def helper(self, st):
		n = len(st)
		for i in range(n - 1):
			if st[i] == st[i + 1] == '1':
				return False
		return True


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		a = 2 ** n
		ans = []
		for i in range(1, a):
			s = bin(i).replace('0b', '')
			for j in range(len(s) - 1):
				if s[j] == '1' and s[j + 1] == '1':
					break
			else:
				ans.append(i)
		return ans


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		(l, l1) = ([], [])
		i = 1
		while True:
			c = str(bin(i))[2:]
			if len(c) > n:
				break
			elif '11' not in c:
				l.append(i)
			i += 1
		l.sort()
		return l


class Solution:

	def numberWithNoConsecutiveOnes(self, n):
		(l, l1) = ([], [])
		i = 1
		while True:
			c = str(bin(i))[2:]
			if len(c) > n:
				break
			if c.count('1') == 1:
				l.append(i)
			else:
				l1.append(c)
			i += 1
		for i in l1:
			if '11' in i:
				pass
			else:
				f = int(i, 2)
				l.append(f)
		l.sort()
		return l