Given a number N, your task is to complete the function which generates all n-bit grey code sequences, a grey code sequence is a sequence such that successive patterns in it differ by one bit.
Example 1:
Input:
N = 2
Output: 00 01 11 10
Explanation: All 2-bit gray codes are
00, 01, 11, 10 such that successive
patterns in it differ by one bit.
Example 2:
Input:
N = 1
Output: 0 1
 
Your Task:
Complete the function generateCode() which takes an integer as input parameter and retruns an array of all N bit grey code sequence such that successive patterns in it differ by one bit.
Expected Time Complexity: O(N * 2^{N})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 16

Difficulty: EASY
Tags: String algorithms

Bit manipulation

Data structures
Skill types: Bit manipulation

Data structures
Expected Time Complexity: O(N * 2^{N})
Expected Auxiliary Space: O(1)

Starter code:
# Your task is to complete this function
# Function should return a list of all the Grey Code Generated
class Solution:
    def generateCode(self, n):
        # Code here

Solutions:
class Solution:

	def generateCode(self, n):
		for i in range(1 << n):
			val = i ^ i >> 1
			s = bin(val)[2:]
			print(s.zfill(n), end=' ')
		return []


class Solution:

	def generateCode(self, n):
		iterations = 1 << n
		ans = []
		ans.append('0' * n)
		for i in range(1, iterations):
			gray = i ^ i >> 1
			gray = str(bin(gray))[2:]
			final_gray = '0' * (n - len(gray)) + gray
			ans.append(final_gray)
		return ans


class Solution:

	def generateCode(self, n):
		if n <= 0:
			return ['0']
		if n == 1:
			return ['0', '1']
		result = []
		rcans = self.generateCode(n - 1)
		for i in range(len(rcans)):
			result.append('0' + rcans[i])
		for j in range(len(rcans) - 1, -1, -1):
			result.append('1' + rcans[j])
		return result


class Solution:

	def generateCode(self, n):
		return ['{:0{n}b}'.format(x ^ x >> 1, n=n) for x in range(1 << n)]


def generateGray(n):
	if n <= 0:
		return ['0']
	if n == 1:
		return ['0', '1']
	recAns = generateGray(n - 1)
	mainAns = []
	for i in range(len(recAns)):
		s = recAns[i]
		mainAns.append('0' + s)
	for i in range(len(recAns) - 1, -1, -1):
		s = recAns[i]
		mainAns.append('1' + s)
	return mainAns

class Solution:

	def generateCode(self, n):
		return generateGray(n)


class Solution:

	def generateCode(self, n):
		if n == 1:
			return ['0', '1']
		ans = self.generateCode(n - 1)
		temp = []
		for i in range(len(ans)):
			temp.append('0' + ans[i])
		for i in range(len(ans) - 1, -1, -1):
			temp.append('1' + ans[i])
		return temp


class Solution:

	def generateCode(self, n):
		if n == 1:
			return ['0', '1']
		elif n == 2:
			return ['00', '01', '11', '10']
		ans = ['00', '01', '11', '10']
		while n > 2:
			l = ans[:]
			r = ans[:][::-1]
			for i in range(len(l)):
				l[i] = '0' + l[i]
				r[i] = '1' + r[i]
			ans = l + r
			n -= 1
		return ans


class Solution:

	def generateCode(self, n):
		return self.grey(n)

	def grey(self, n):
		if n <= 0:
			return ['0']
		if n == 1:
			return ['0', '1']
		res = self.grey(n - 1)
		c = []
		for i in range(len(res)):
			s = res[i]
			c.append('0' + s)
		for i in range(len(res) - 1, -1, -1):
			s = res[i]
			c.append('1' + s)
		return c


class Solution:

	def generateCode(self, n):
		if n == 0:
			return ['0']
		if n == 1:
			return ['0', '1']
		rec_Ans = self.generateCode(n - 1)
		max_Ans = []
		for i in range(len(rec_Ans)):
			s = rec_Ans[i]
			max_Ans.append('0' + s)
		for j in range(len(rec_Ans) - 1, -1, -1):
			s = rec_Ans[j]
			max_Ans.append('1' + s)
		return max_Ans


class Solution:

	def generateCode(self, n):

		def getCode(index, temp):
			if index == n:
				return temp
			result = []
			for i in range(len(temp)):
				val = temp[i]
				val = '0' + val
				result.append(val)
			for i in range(len(temp) - 1, -1, -1):
				val = temp[i]
				val = '1' + val
				result.append(val)
			return getCode(index + 1, result)
		result = ['0', '1']
		return getCode(1, result)


class Solution:

	def generateCode(self, n):
		if n == 0:
			return []
		codes = []
		if n >= 1:
			codes.append('0')
			codes.append('1')
		for _ in range(2, n + 1):
			newCodes = []
			for code in codes:
				newCodes.append('0' + code)
			for code in reversed(codes):
				newCodes.append('1' + code)
			codes = newCodes
		return codes


class Solution:

	def generateCode(self, n):
		if n <= 0:
			return
		array = list()
		array.extend(['0', '1'])
		(i, j) = (2, 0)
		while True:
			if i >= 1 << n:
				break
			for j in range(i - 1, -1, -1):
				array.append(array[j])
			for j in range(i):
				array[j] = '0' + array[j]
			for j in range(i, 2 * i):
				array[j] = '1' + array[j]
			i = i << 1
		return array


class Solution:

	def generateCode(self, n):

		def helper(n):
			if n == 1:
				return ['0', '1']
			curr = []
			k = helper(n - 1)
			l = len(k)
			for i in range(l):
				a = '0' + k[i]
				curr.append(a)
			k = k[::-1]
			for i in range(l):
				a = '1' + k[i]
				curr.append(a)
			return curr
		return helper(n)


class Solution:

	def generateCode(self, n):
		l = ['0', '1']
		while len(l[-1]) != n:
			b = []
			for i in l:
				if i.count('1') % 2 == 0:
					b.append(i + '0')
					b.append(i + '1')
				else:
					b.append(i + '1')
					b.append(i + '0')
			l = b
		return l


class Solution:

	def generateCode(self, n):
		lst = ['0', '1']
		if n == 1:
			return lst
		i = 2
		while True:
			if i >= 1 << n:
				break
			for j in range(i - 1, -1, -1):
				lst.append(lst[j])
			for j in range(i):
				lst[j] = '0' + lst[j]
			for j in range(i, i * 2):
				lst[j] = '1' + lst[j]
			i = i << 1
		return lst


class Solution:

	def generateCode(self, n):
		l = []
		for i in range(0, pow(2, n)):
			l.append(bin(i ^ i >> 1)[2:].zfill(n))
		return l


class Solution:

	def get_next_pattern(self, arr):
		mirror = arr[::-1]
		for i in range(len(arr)):
			arr[i] = '0' + arr[i]
			mirror[i] = '1' + mirror[i]
		new = arr + mirror
		return new

	def generateCode(self, n):
		start = ['0', '1']
		count = 1
		while count < n:
			start = self.get_next_pattern(start)
			count += 1
		return start


class Solution:

	def generateCode(self, n):
		N = 1 << n
		res = []
		for i in range(N):
			x = i ^ i >> 1
			b = bin(x).replace('0b', '')
			ln = n - len(b)
			ans = '0' * ln + b
			res.append(ans)
		return res
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		res = Solution().generateCode(int(input()))
		for j in range(len(res)):
			print(res[j], end=' ')
		print()


class Solution:

	def generateCode(self, n):
		ans = []
		for i in range(1 << n):
			k = i ^ i >> 1
			l = format(k, '016b')
			ans.append(l[16 - n:])
		return ans
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		res = Solution().generateCode(int(input()))
		for j in range(len(res)):
			print(res[j], end=' ')
		print()


class Solution:

	def generateCode(self, n):
		ans = ['0', '1']
		j = 0
		for i in range(1, n):
			ans = ans + ans[::-1]
			for j in range(2 ** i):
				ans[j] = '0' + ans[j]
			for k in range(j + 1, 2 ** (i + 1)):
				ans[k] = '1' + ans[k]
		return ans


class Solution:

	def generateCode(self, n):
		base = ['0', '1']
		if n == 1:
			return base
		for i in range(1, n):
			for i in range(len(base) - 1, -1, -1):
				base.append('1' + base[i])
			for i in range(len(base) // 2):
				base[i] = '0' + base[i]
		return base


class Solution:

	def generateCode(self, n):
		res = ['0', '1']
		if n == 1:
			return res
		while n > 1:
			var = list()
			for ele in res:
				var.append('0' + ele)
			for ele in reversed(res):
				var.append('1' + ele)
			res = var
			n -= 1
		return res


class Solution:

	def generateCode(self, n):
		out = ['0', '1']
		if n == 1:
			return out
		else:
			k = 1
			while k < n:
				for i in range(len(out) - 1, -1, -1):
					out.append(out[i])
				for i in range(0, len(out) // 2):
					out[i] = '0' + out[i]
				for i in range(len(out) // 2, len(out)):
					out[i] = '1' + out[i]
				k += 1
			return out


class Solution:

	def generateCode(self, n):
		if n == 1:
			return ['0', '1']
		prev_grey_code = self.generateCode(n - 1)
		current_grey_code = []
		for ele in prev_grey_code:
			current_grey_code.append('0' + ele)
		for ele in reversed(prev_grey_code):
			current_grey_code.append('1' + ele)
		return current_grey_code


class Solution:

	def generateCode(self, n):
		arr = []
		if n <= 0:
			return arr
		arr.append('0')
		arr.append('1')
		i = 2
		j = 0
		while i < 1 << n:
			j = i - 1
			while j >= 0:
				arr.append(arr[j])
				j -= 1
			for j in range(0, i):
				arr[j] = '0' + arr[j]
			j = i
			while j < 2 * i:
				arr[j] = '1' + arr[j]
				j += 1
			i = i << 1
		return arr


class Solution:

	def dectobin(self, num, n):
		tmp_string = ['0'] * n
		i = 0
		while num > 0:
			if num % 2 != 0:
				tmp_string[n - i - 1] = '1'
			num = num // 2
			i += 1
		return ''.join(tmp_string)

	def generateCode(self, n):
		tmp_list = []
		num_seq = 2 ** n
		for i in range(num_seq):
			grey_code = i ^ i >> 1
			tmp_list.append(self.dectobin(grey_code, n))
		return tmp_list


class Solution:

	def generateCode(self, n):
		if n == 1:
			return ['0', '1']
		prev = self.generateCode(n - 1)
		ls = []
		for i in prev:
			s = '0' + i
			ls.append(s)
		for i in ls[::-1]:
			s = '1' + i[1:]
			ls.append(s)
		return ls


class Solution:

	def generateCode(self, n):
		ans = ['0', '1']
		for e in range(n - 1):
			a = ans
			b = ans.copy()
			b.reverse()
			L = len(a)
			for i in range(L):
				a[i] = '0' + a[i]
			for i in range(L):
				b[i] = '1' + b[i]
			ans = a + b
		return ans


class Solution:

	def generateCode(self, n):
		N = 1 << n
		l = []
		for i in range(N):
			x = i ^ i >> 1
			a = list(bin(x)[2:])
			if len(a) < len(bin(N)) - 3:
				c = len(bin(N)) - 3 - len(a)
				for j in range(c):
					a.insert(0, '0')
			l.append(''.join(a))
		return l


from collections import OrderedDict

class Solution:

	def generateCode(self, n):
		ans = OrderedDict()
		curr = ['0'] * n
		ans[''.join(curr)] = 1
		total = 2 ** n
		while len(ans) != total:
			for i in range(n - 1, -1, -1):
				if curr[i] == '0':
					curr[i] = '1'
					if not ans.get(''.join(curr), 0):
						ans[''.join(curr)] = 1
						break
					else:
						curr[i] = '0'
				else:
					curr[i] = '0'
					if not ans.get(''.join(curr), 0):
						ans[''.join(curr)] = 1
						break
					else:
						curr[i] = '1'
		return list(ans.keys())


class Solution:

	def generateCode(self, n):
		l = []
		for i in range(0, 1 << n):
			gray = i ^ i >> 1
			l.append('{0:0{1}b}'.format(gray, n))
		return l


class Solution:

	def binary(self, number, length):
		b = format(number, 'b')
		b = '0' * (length - len(b)) + b
		return b

	def generateCode(self, n):
		result = []
		for i in range(2 ** n):
			result.append(self.binary(i ^ i >> 1, n))
		return result


class Solution:

	def generateCode(self, n):

		def add(val, n, res, arr):
			if n == 1:
				arr += str(val)
				return arr
			arr += str(val)
			value = add(0, n - 1, res, arr)
			if value is not None:
				res.append(value)
			value = add1(1, n - 1, res, arr)
			if value is not None:
				res.append(value)

		def add1(val, n, res, arr):
			if n == 1:
				arr += str(val)
				return arr
			arr += str(val)
			value = add(1, n - 1, res, arr)
			if value is not None:
				res.append(value)
			value = add1(0, n - 1, res, arr)
			if value is not None:
				res.append(value)
		res = []
		value = add(0, n, res, '')
		if value is not None:
			res.append(value)
		value = add1(1, n, res, '')
		if value is not None:
			res.append(value)
		return res


class Solution:

	def generateCode(self, n):
		if n == 1:
			return ['0', '1']
		greyCodesForNminusOne = self.generateCode(n - 1)
		greyCodes = []
		for i in range(len(greyCodesForNminusOne)):
			code = greyCodesForNminusOne[i]
			greyCodes.append('0' + code)
		for i in range(len(greyCodesForNminusOne) - 1, -1, -1):
			code = greyCodesForNminusOne[i]
			greyCodes.append('1' + code)
		return greyCodes


class Solution:

	def generateCode(self, n):
		bitslist = []
		if n == 1:
			return ['0', '1']
		returnlist = Solution().generateCode(n - 1)
		[bitslist.append('0' + item) for item in returnlist]
		[bitslist.append('1' + item) for item in returnlist[::-1]]
		return bitslist


from copy import deepcopy

class Solution:

	def generateCode(self, n):
		arr = []
		arr.append('0')
		arr.append('1')
		if n == 1:
			return arr
		while n > 1:
			a = []
			for i in arr:
				a.append('0' + i)
			for i in range(len(arr) - 1, -1, -1):
				a.append('1' + arr[i])
			arr = []
			arr = deepcopy(a)
			n -= 1
		return a


class Solution:

	def Reverse(self, lst):
		return [ele for ele in reversed(lst)]

	def generateCode(self, n):
		a = ['0', '1']
		b = self.Reverse(a)
		for i in range(1, n):
			for j in range(0, len(a)):
				a[j] = '0' + a[j]
			for k in range(0, len(b)):
				b[k] = '1' + b[k]
			a = a + b
			b = self.Reverse(a)
		return a


class Solution:

	def generateCode(self, num):
		if num == 1:
			return [0, 1]
		l1 = Solution().generateCode(num - 1)
		l2 = l1[::-1]
		for i in range(len(l1)):
			l1[i] = '0' + str(l1[i])
		for i in range(len(l2)):
			l2[i] = '1' + str(l2[i])
		return l1 + l2


class Solution:

	def generateCode(self, n):

		def gen_code(n):
			if n == 0:
				return ['0']
			if n == 1:
				return ['0', '1']
			L = gen_code(n - 1)
			res = []
			for i in range(len(L)):
				res.append('0' + L[i])
			for i in range(len(L) - 1, -1, -1):
				res.append('1' + L[i])
			return res
		return gen_code(n)


class Solution:

	def generateCode(self, n):
		L = []
		for x in range(2 ** n):
			Number = x ^ x >> 1
			Binary_Number = bin(Number)[2:]
			Length = len(Binary_Number)
			L.append('0' * (n - Length) + Binary_Number)
		return L


class Solution:

	def generateCode(self, n):
		out = ['0', '1']
		if n == 1:
			return out
		else:
			limit = 2 ** n
			m = 2
			while m < limit:
				for i in range(len(out) - 1, -1, -1):
					out.append(out[i])
				for i in range(len(out) // 2):
					out[i] = '0' + out[i]
				for j in range(len(out) // 2, len(out)):
					out[j] = '1' + out[j]
				m = m << 1
			return out