Given a number N, generate bit patterns from 0 to 2^N-1 such that successive patterns differ by one bit. 
A Gray code sequence must begin with 0.
 
Example 1:
Input:
N = 2
Output: 
00 01 11 10
Explanation: 
00 and 01 differ by one bit.
01 and 11 differ by one bit.
11 and 10 also differ by one bit.
 
Example 2:
Input:
N=3
Output:
000 001 011 010 110 111 101 100
Explanation:
000 and 001 differ by one bit.
001 and 011 differ by one bit.
011 and 010 differ by one bit.
Similarly, every successive pattern 
differs by one bit.
Your task:
You don't need to read input or print anything. Your task is to complete the function graycode() which takes an integer N as input and returns a la list of patterns.
 
Expected Time Complexity: O(2^{n})
Expected Auxiliary Space: O(2^{n})
 
Constraints :
1<=N<=16

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Complete search

Starter code: #User function Template for python3

class Solution:
    def graycode(self,n):
        #code here

Solutions:
class Solution:

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


class Solution:

	def graycode(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 graycode(self, n):
		g = [x ^ x >> 1 for x in range(1 << n)]
		return ['{:0{n}b}'.format(x, n=n) for x in g]


class Solution:

	def graycode(self, n):
		if n == 1:
			return ['0', '1']
		arr = self.graycode(n - 1)
		arr2 = []
		for i in range(len(arr)):
			arr2.append('0' + arr[i])
		for j in range(len(arr) - 1, -1, -1):
			arr2.append('1' + arr[j])
		return arr2


class Solution:

	def graycode(self, n):
		if n == 1:
			return ['0', '1']
		else:
			prev_gray = self.graycode(n - 1)
			reflected_gray = prev_gray[::-1]
		gray = []
		for code in prev_gray:
			gray.append('0' + code)
		for code in reflected_gray:
			gray.append('1' + code)
		return gray


def bina(st, ind, res, n):
	if ind == n:
		res.append(st)
		return
	bina(st + '0', ind + 1, res, n)
	bina(st + '1', ind + 1, res, n)

class Solution:

	def graycode(self, n):
		res = []
		ans = []
		bina('', 0, res, n)
		for i in range(len(res)):
			st = res[i][0]
			for j in range(1, len(res[i])):
				temp = str(int(res[i][j - 1]) ^ int(res[i][j]))
				st = st + temp
			ans.append(st)
		return ans


class Solution:

	def graycode(self, n):
		return [format(int(x ^ x >> 1), '0' + str(n) + 'b') for x in range(2 ** n)]


class Solution:

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


class Solution:

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

	def graycode(self, n):
		res = list()
		return self.util(n, res)
		return res


class Solution:

	def graycode(self, n):

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


class Solution:

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


class Solution:

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


import math

class Solution:

	def graycode(self, n):
		ans = []
		base = '0' * n
		ans.append(base)
		if n == 0:
			return ['0']
		else:
			num = 1
			j = -1
			s = list(base)
			while num < 2 ** n:
				if num == 1:
					s[-1] = '1'
				else:
					index = 0 - (math.floor(math.log(num, 2)) + 1)
					s[index] = '1'
					s[index + 1:] = ans[j][index + 1:]
					if ans[j] == ans[0]:
						j = -1
					else:
						j -= 2
				ans.append(''.join(s))
				num += 1
			return ans


class Solution:

	def graycode(self, n):
		myList = ['0', '1']
		for i in range(n - 1):
			for j in range(len(myList) - 1, -1, -1):
				myList.append(myList[j])
			for k in range(len(myList) // 2):
				myList[k] = '0' + myList[k]
			for l in range(len(myList) // 2, len(myList)):
				myList[l] = '1' + myList[l]
		return myList


class Solution:

	def graycode(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 graycode(self, n):

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


class Solution:

	def graycode(self, n):

		def funk(n):
			if n == 1:
				return ['0', '1']
			b = funk(n - 1)
			c = []
			for r in range(2 ** (n - 1)):
				c += ['0' + b[r]]
			for rr in range(2 ** (n - 1) - 1, -1, -1):
				c += ['1' + b[rr]]
			return c
		return funk(n)


class Solution:

	def graycode(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 graycode(self, n):
		ii = 1
		temp = ['0', '1']
		if n == 1:
			return temp
		while ii < n:
			tempp = []
			for i in range(len(temp)):
				tempp.append('0' + temp[i])
			for i in range(len(temp) - 1, -1, -1):
				tempp.append('1' + temp[i])
			temp = tempp
			ii += 1
		return tempp


class Solution:

	def graycode(self, n):
		if n < 1:
			return []
		out = []
		out.append(format(0, '0' + str(n) + 'b'))
		c = int(math.pow(2, n))
		for i in range(1, c):
			v = i ^ i >> 1
			out.append(format(v, '0' + str(n) + 'b'))
		return out


class Solution:

	def graycode(self, n):

		def generateGray(n):
			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

		def generateGrayarr(n):
			arr = generateGray(n)
			return arr
		return generateGrayarr(n)


class Solution:

	def graycode(self, n):
		patterns = []
		i = 0
		while i < 1 << n:
			val = i ^ i >> 1
			gray = bin(val).replace('0b', '').zfill(n)
			patterns.append(gray)
			i += 1
		return patterns


class Solution:

	def graycode(self, n):

		def dec2bin(d):
			return bin(d).replace('0b', '').zfill(n)
		patterns = ['0' * n]
		for i in range(1, 2 ** n):
			b = dec2bin(i)
			g = b[0]
			for j in range(1, n):
				g += str(int(b[j]) ^ int(b[j - 1]))
			patterns.append(g)
		return patterns


class Solution:

	def graycode(self, n):
		ans = ['0', '1']
		if n == 1:
			return ans
		for i in range(1, n):
			add0 = ans[:]
			for j in range(len(ans)):
				add0[j] = '0' + add0[j]
			add1 = ans[::-1]
			for j in range(len(ans)):
				add1[j] = '1' + add1[j]
			ans = add0 + add1
		return ans


class Solution:

	def graycode(self, n):
		length = 1 << n
		output = []
		for i in range(length):
			num = i ^ i >> 1
			bin_num = bin(num)[2:].zfill(n)
			output.append(bin_num)
		return output


class Solution:

	def graycode(self, n):
		l = [[0, 1]]
		for i in range(2, n + 1):
			modified = ['0' + str(i) for i in l[-1]]
			modified_rev = ['1' + str(i) for i in l[-1][::-1]]
			l.append(modified + modified_rev)
		return l[-1]


class Solution:

	def graycode(self, n):
		arr = []
		for i in range(1 << n):
			val = i ^ i >> 1
			s = bin(val)[2:]
			arr.append(s.zfill(n))
		return arr


class Solution:

	def graycode(self, n):
		arr = []
		for i in range(2 ** n):
			x = bin(i).replace('0b', '').rjust(n, '0')
			a = x[0]
			for j in range(1, len(x)):
				a += str(int(x[j - 1]) ^ int(x[j]))
			arr.append(a)
		return arr


class Solution:

	def graycode(self, n):
		ans = ['0', '1']
		if n == 1:
			return ans
		for i in range(2, n + 1):
			new_ans = []
			for j in ans:
				new_ans.append('0' + j)
			for j in ans[::-1]:
				new_ans.append('1' + j)
			ans = new_ans
		return ans


class Solution:

	def graycode(self, n):

		def rec(res, i, n):
			if i == n:
				return
			temp = res[-1]
			row = []
			for j in range(len(temp)):
				row.append('0' + str(temp[j]))
			for j in range(len(temp) - 1, -1, -1):
				row.append('1' + str(temp[j]))
			res.append(row)
			return rec(res, i + 1, n)
		res = []
		res.append([0, 1])
		rec(res, 1, n)
		return res[-1]
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		if n == 0:
			return 0
		if n == 1:
			return [0, 1]
		array = []
		for i in range(pow(2, n)):
			array.append(str(bin(i ^ i >> 1)))
			array[i] = array[i][2:]
			if len(array[i]) < n:
				array[i] = (n - len(array[i])) * '0' + array[i]
		return array
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def mult(self, lst):
		res = []
		for j in lst:
			res.append('0' + j)
		for j in reversed(lst):
			res.append('1' + j)
		return res

	def intTobin(self, num):
		ans = ''
		while num:
			ans += str(num % 2)
			num = num // 2
		return ans[::-1]

	def graycode(self, n):
		lst = ['0', '1']
		for i in range(n - 1):
			lst = self.mult(lst)
		return lst
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		return [format(int(x ^ x >> 1), '0' + str(n) + 'b') for x in range(2 ** n)]
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		if n == 1:
			return [str(0), str(1)]
		else:
			ans = []
			a = self.graycode(n - 1)
			for i in range(len(a)):
				ans.append(str(0) + a[i])
			for i in range(len(a) - 1, -1, -1):
				ans.append(str(1) + a[i])
			return ans
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		l1 = ['0', '1']
		for i in range(2, n + 1):
			l2 = []
			for i in range(len(l1) - 1, -1, -1):
				l2.append(l1[i])
			for i in range(len(l1)):
				l1[i] = '0' + l1[i]
			for i in range(len(l2)):
				l2[i] = '1' + l2[i]
			l1.extend(l2)
		return l1
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		a = ['0', '1']
		i = 1
		while i < n:
			m = len(a)
			for j in range(m - 1, -1, -1):
				k = a[j]
				l = len(a[i])
				if l != i:
					gg = i - l
					for f in range(gg):
						a[i] = '0' + a[i]
				k = '1' + k
				a.append(k)
			for p in range(m):
				a[p] = '0' + a[p]
			i += 1
		return a
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		if n == 1:
			return ['0', '1']
		miniarr = []
		res = self.graycode(n - 1)
		for i in res:
			miniarr.append('0' + i)
		for i in res[::-1]:
			miniarr.append('1' + i)
		return miniarr
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		temp1 = ['0', '1']
		for i in range(2, n + 1):
			temp2 = []
			for j in range(len(temp1)):
				temp2.append('0' + temp1[j])
			for j in range(len(temp1) - 1, -1, -1):
				temp2.append('1' + temp1[j])
			temp1 = temp2[:]
		return temp1
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		ans = []
		for i in range(1 << n):
			k = i ^ i >> 1
			l = format(k, '016b')
			ans.append(l[16 - n:])
		return ans
import math

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		ob = Solution()
		l = ob.graycode(n)
		for x in l:
			print(x, end=' ')
		print()
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def graycode(self, n):
		grey = []
		i = 0
		while i < 1 << n:
			val = i ^ i >> 1
			s = ''
			j = 0
			while j < n:
				if val & 1 << j != 0:
					s = '1' + s
				else:
					s = '0' + s
				j += 1
			i += 1
			grey.append(s)
		return grey


import math

class Solution:

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


class Solution:

	def graycode(self, n):
		ans = []
		for i in range(1 << n):
			val = i ^ i >> 1
			bitrep = format(val, '016b')
			ans.append(bitrep[16 - n:])
		return ans


class Solution:

	def graycode(self, n):

		def rec(i, n, res):
			if i == n:
				return res[-1]
			row = []
			temp = res[-1]
			for j in range(len(temp)):
				row.append('0' + str(temp[j]))
			for j in range(len(temp) - 1, -1, -1):
				row.append('1' + str(temp[j]))
			res.append(row)
			return rec(i + 1, n, res)
		res = []
		res.append([0, 1])
		return rec(1, n, res)


class Solution:

	def graycode(self, n):
		if n == 0:
			res = []
			res.append('')
			return res
		prev = self.graycode(n - 1)
		res = []
		if len(prev) == 0:
			res.append('0')
			res.append('1')
		else:
			for i in range(len(prev)):
				if i % 2 == 0:
					res.append(prev[i] + '0')
					res.append(prev[i] + '1')
				else:
					res.append(prev[i] + '1')
					res.append(prev[i] + '0')
		return res


class Solution:

	def graycode(self, n):
		ans = []
		for i in range(1 << n):
			val = i ^ i >> 1
			string = ''
			while val:
				string += str(val % 2)
				val //= 2
			while len(string) < n:
				string += '0'
			ans.append(string[::-1])
		return ans


class Solution:

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


class Solution:

	def graycode(self, n):
		output = []
		padding = '0{}b'.format(n)
		code = '0' * n
		for i in range(1 << n):
			output.append(format(i ^ i >> 1, padding))
		return output


class Solution:

	def graycode(self, n):
		ans = []
		for i in range(1 << n):
			s = ['0'] * n
			k = 0
			for j in range(n):
				if i & 1 << j:
					s[n - 1 - j] = '1'
			s = ''.join(s)
			g = s[0]
			for k in range(1, n):
				if s[k] == s[k - 1]:
					g += '0'
				else:
					g += '1'
			ans.append(g)
		return ans


class Solution:

	def graycode(self, n):
		if n == 1:
			return ['0', '1']
		l1 = self.graycode(n - 1)
		l2 = reversed(l1)
		modl1 = ['0' + i for i in l1]
		modl2 = ['1' + i for i in l2]
		return modl1 + modl2


class Solution:

	def graycode(self, n):
		N = 2 ** n
		code = '0' * n
		result = [code]
		for i in range(1, N):
			for flip_bit in range(n, -1, -1):
				if i % 2 ** flip_bit == 0:
					flip_bit = n - flip_bit - 1
					break
			code = code[:flip_bit] + ('0' if code[flip_bit] == '1' else '1') + code[flip_bit + 1:]
			result.append(code)
		return result


class Solution:

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


class Solution:

	def graycode(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 graycode_gen(self, n: int):
		if n == 0:
			return ['0']
		if n == 1:
			return ['0', '1']
		arr = self.graycode_gen(n - 1)
		res = []
		L = len(arr)
		for i in range(L):
			res.append('0' + arr[i])
		for i in range(L - 1, -1, -1):
			res.append('1' + arr[i])
		return res

	def graycode(self, n):
		return self.graycode_gen(n)


class Solution:

	def graycode_gen(self, n: int):
		if n == 0:
			return ['0']
		if n == 1:
			return ['0', '1']
		arr = self.graycode_gen(n - 1)
		res = []
		for i in arr:
			res.append('0' + i)
		for i in reversed(arr):
			res.append('1' + i)
		return res

	def graycode(self, n):
		return self.graycode_gen(n)


class Solution:

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


class Solution:

	def graycode(self, n):
		if n == 1:
			return ['0', '1']
		else:
			a = self.graycode(n - 1)
			Final = []
			for i in range(len(a)):
				Final.append('0' + a[i])
			Second = []
			for i in range(len(a)):
				Second.append('1' + a[i])
			Second = Second[::-1]
			Final.extend(Second)
			return Final


class Solution:

	def gray(self, n):
		if n == 1:
			l = ['0', '1']
			return l
		l = self.gray(n - 1)
		res = []
		for i in l:
			res.append('0' + i)
		for i in reversed(l):
			res.append('1' + i)
		return res

	def graycode(self, n):
		l = self.gray(n)
		return l


from itertools import permutations

class Solution:

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


from collections import deque

class Solution:

	def graycode(self, n):
		if n == 1:
			return ['0', '1']
		rec = self.graycode(n - 1)
		new = []
		for x in rec:
			new.append('0' + x)
		for x in rec[::-1]:
			new.append('1' + x)
		return new


class Solution:

	def graycode(self, n):
		N = n
		res = []
		for i in range(2 ** N):
			s = str((i & 1 << N - 1) >> N - 1)
			for j in range(1, N):
				p = (i & 1 << N - j - 1) >> N - j - 1
				q = (i & 1 << N - j) >> N - j
				s += str(p ^ q)
			res.append(s)
		return res


import math

class Solution:

	def toBinary(self, num, a):
		res = list()
		while num > 0:
			n = num % 2
			res.append(n)
			num //= 2
		l = a - len(res)
		for i in range(l):
			res.append(0)
		res.reverse()
		return res

	def toGray(self, b, n):
		r = list()
		r.append(str(b[0]))
		for i in range(1, n):
			r.append(str(b[i] ^ b[i - 1]))
		return ''.join(r)

	def graycode(self, n):
		res = list()
		for i in range(int(math.pow(2, n))):
			b = self.toBinary(i, n)
			r = self.toGray(b, n)
			res.append(r)
		return res


class Solution:

	def graycode(self, n):
		res = ['0', '1']
		if n == 1:
			return res
		curr = 1
		while curr < n:
			temp = []
			for x in res:
				temp.append('0' + x)
			for x in res[::-1]:
				temp.append('1' + x)
			res = temp
			curr += 1
		return res


class Solution:

	def graycode(self, n):

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


class Solution:

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


class Solution:

	def graycode(self, n):

		def convertStringToList(string):
			resultingList = []
			resultingList[:0] = string
			return resultingList
		baseList = ['0' * n]
		for i in range(n - 1, -1, -1):
			listLastIndex = len(baseList) - 1
			for j in range(listLastIndex, -1, -1):
				stringToList = convertStringToList(baseList[j])
				stringToList[i] = '1'
				listToString = ''.join(stringToList)
				baseList.append(listToString)
		return baseList


class Solution:

	def graycode(self, n):

		def convert(string):
			list1 = []
			list1[:0] = string
			return list1
		arr = ['0' * n]
		for i in range(n - 1, -1, -1):
			arrLen = len(arr) - 1
			for j in range(arrLen, -1, -1):
				strtoarr = convert(arr[j])
				strtoarr[i] = '1'
				stragain = ''.join(strtoarr)
				arr.append(stragain)
		return arr


class Solution:

	def graycode(self, n):
		res = [0, 1]
		if n == 1:
			return res
		else:
			for i in range(1, n):
				val = pow(2, i)
				cur = []
				for j in range(len(res) - 1, -1, -1):
					cur.append(val + res[j])
				res = res + cur
			final = []
			for i in res:
				k = bin(i)[2:]
				a = n - len(k)
				k = '0' * a + k
				final.append(k)
			return final


class Solution:

	def gcode(self, temp1, temp2):
		for i in range(len(temp1)):
			temp1[i] = '0' + temp1[i]
		for j in range(len(temp2)):
			temp2[j] = '1' + temp2[j]
		return (temp1, temp2)

	def graycode(self, n):
		temp1 = ['0']
		temp2 = ['1']
		for i in range(2, n + 1):
			a = temp1 + temp2
			b = a[::-1]
			(temp1, temp2) = self.gcode(a, b)
		return temp1 + temp2


class Solution:

	def graycode(self, n):
		a = ['0', '1']
		len_a = 2
		for i in range(1, n):
			for j in range(len_a - 1, -1, -1):
				a.append('1' + a[j])
			for j in range(len_a):
				a[j] = '0' + a[j]
			len_a *= 2
		return a


class Solution:

	def graycode(self, n):
		res = ['0', '1']
		(x, y) = ('0', '1')
		for j in range(n - 1):
			cur = []
			for i in range(len(res)):
				cur.append(res[i] + x)
				cur.append(res[i] + y)
				(x, y) = (y, x)
			res = cur
		return res