You are given a decimal number n. You need to find the gray code of the number n and convert it into decimal.
Gray code is a binary numeral system where two successive values differ in only one bit.
For example, the sequence of Gray codes for 3-bit numbers is: 000, 001, 011, 010, 110, 111, 101, 100, so G(4)=6.
Example 1:
Input:
n  = 7
Output:
4
Explanation:
7 is represented as 111 in binary form.
The gray code of 111 is 100, in the binary
form whose decimal equivalent is 4.
Example 2:
Input:
n  = 10
Output:
15
Explanation:
10 is represented as 1010 in binary form.
The gray code of 1010 is 1111, in the binary
form whose decimal equivalent is 15.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function getGray() which takes an Integer n as input and returns the answer.
 
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
 
Constraints:
0 <= n <= 10^{8}

Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics
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 getGray(self, n):
        # code here 

Solutions:
class Solution:

	def getGray(self, n):
		return n ^ n >> 1


class Solution:

	def getGray(self, n):
		return n ^ n // 2


class Solution:

	def getGray(self, n):
		b = bin(n)[2:]
		r = b[::-1]
		s = ''
		for i in range(len(r) - 1):
			s += str(int(r[i]) ^ int(r[i + 1]))
		a = s + b[0]
		return int(str(a)[::-1], 2)


class Solution:

	def getGray(self, n):
		if n == 0:
			return 0
		while n:
			n = n ^ n >> 1
			return n


import math

class Solution:

	def getGray(self, n):
		return n ^ n >> 1


class Solution:

	def getGray(self, n):
		b = bin(n)[2:]
		e = b[0]
		for i in range(len(b) - 1):
			e += str(int(b[i]) ^ int(b[i + 1]))
		return int(e, 2)


class Solution:

	def getGray(self, n):
		b = bin(n).replace('0b', '')
		s = ''
		s += b[0]
		for i in range(len(b) - 1):
			s = s + str(int(b[i]) ^ int(b[i + 1]))
		return int(s, 2)


class Solution:

	def getGray(self, n):
		q = n >> 1
		ans = n ^ q
		return ans


class Solution:

	def getGray(self, n):
		b = bin(n)[2:]
		if len(b) == 1:
			return int(b)
		if b[0] == '1':
			c = '0' + b[:-1]
		else:
			c = '1' + b[:-1]
		return int(b, 2) ^ int(c, 2)


class Solution:

	def getGray(self, n):
		n ^= n >> 1
		n = bin(n)[2:]
		return int(n, 2)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.getGray(n))


class Solution:

	def getGray(self, n):
		binum = '{0:b}'.format(int(n))
		graycode = binum[0]
		for i in range(len(binum) - 1):
			x = int(binum[i]) ^ int(binum[i + 1])
			graycode += str(x)
		return int(graycode, 2)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.getGray(n))


class Solution:

	def getGray(self, n):
		return n ^ n >> 1
		if n == 1:
			ans = []
			ans.append('0')
			ans.append('1')
			return ans
		res = self.getGray(n - 1)
		ans1 = []
		for i in range(len(res)):
			ans1.append('0' + res[i])
		for i in range(len(res)):
			ans1.append('1' + res[i])
		return ans1[7]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.getGray(n))


class Solution:

	def getGray(self, n):
		if n == 0:
			return 0
		a = 1
		while a * 2 <= n:
			a *= 2
		return a + self.getGray(2 * a - n - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.getGray(n))


class Solution:

	def getGray(self, n):
		s = bin(n)
		s = s[2:]
		d = len(s)
		t = s[0]
		g = '1'
		for i in range(d - 1):
			if s[i] == s[i + 1]:
				g = '0'
			else:
				g = '1'
			t += g
		c = 0
		d = d - 1
		for i in t:
			if i == '1':
				c += 2 ** d
			d = d - 1
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.getGray(n))


class Solution:

	def getGray(self, n):
		b = bin(n)
		b = b.replace('0b', '')
		s = str(b)
		ans = '' + s[0]
		for i in range(len(s) - 1):
			if s[i] == '0' and s[i + 1] == '1' or (s[i] == '1' and s[i + 1] == '0'):
				ans += '1'
			else:
				ans += '0'
		return int(ans, 2)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.getGray(n))


import math

class Solution:

	def getGray(self, n):
		x = bin(n)[2:]
		x = list(map(int, x))
		x.reverse()
		ans = 0
		for i in range(len(x) - 1):
			ans += (x[i] ^ x[i + 1]) * 2 ** i
		ans += x[-1] * 2 ** (len(x) - 1)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		print(ob.getGray(n))


class Solution:

	def getGray(self, n):
		n = bin(n)[2:]
		k = n[0]
		for i in range(1, len(n)):
			if n[i] == n[i - 1]:
				k += '0'
			else:
				k += '1'
		return int(k, 2)


class Solution:

	def getGray(self, a):
		n = '{0:b}'.format(int(a))
		n = int(n, 2)
		n ^= n >> 1
		b = bin(n)[2:]
		return int(b, 2)


class Solution:

	def getGray(self, n):
		binary = bin(n)[2:]
		result = binary[0]
		decimal_form = 0
		power = 0
		for i in range(1, len(binary)):
			result += str(int(binary[i - 1]) ^ int(binary[i]))
		result = result[::-1]
		for i in range(len(result)):
			if int(result[i]):
				decimal_form += 2 ** power
			power += 1
		return decimal_form


class Solution:

	def getGray(self, n):
		x = bin(n)[2:]
		x = int(x, 2)
		x ^= x >> 1
		x = bin(x)[2:]
		return int(x, 2)


import math

class Solution:

	def getGray(self, n):
		if n in [0, 1]:
			return n
		result = 0
		index = self.getLength(n)
		previousBit = None
		while index:
			currentBit = n >> index - 1 & 1
			if previousBit == None:
				result = result | currentBit << index - 1
			else:
				result = result | (currentBit ^ previousBit) << index - 1
			previousBit = currentBit
			index -= 1
		return result

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


class Solution:

	def getGray(self, n):
		bi = list(bin(n)[2:])
		fl = [bi[0]]
		for i in range(1, len(bi)):
			fl.append(str(abs(int(bi[i]) - int(bi[i - 1]))))
		return int(''.join(fl), 2)


class Solution:

	def flip(self, c):
		return '1' if c == '0' else '0'

	def getGray(self, n):
		n = bin(n).replace('0b', '')
		gray = ''
		gray += n[0]
		for i in range(1, len(n)):
			if n[i - 1] == n[i]:
				gray += '0'
			else:
				gray += '1'
		return int(gray, 2)


class Solution:

	def getGray(self, n):
		b = str(bin(n))[2:]
		res = str(b[0])
		for i in range(0, len(b) - 1):
			if not int(b[i]) and (not int(b[i + 1])):
				res += '0'
			elif int(b[i]) and int(b[i + 1]):
				res += '0'
			else:
				res += '1'
		return int(res, 2)


class Solution:

	def getGray(self, n):
		s = bin(n)
		s = s[2:]
		g = s[0]
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				g += '0'
			else:
				g += '1'
		ans = 0
		g = g[::-1]
		for i in range(len(g)):
			if g[i] == '1':
				ans += 1 << i
		return ans


class Solution:

	def getGray(self, n):
		if n == 0:
			return 0
		x = 1
		while x * 2 <= n:
			x *= 2
		return x + self.getGray(2 * x - n - 1)


class Solution:

	def getGray(self, n):
		c = 0
		i = 0
		while n > 0:
			a = n % 2
			n = n // 2
			b = n % 2
			c = c + (a ^ b) * 2 ** i
			i = i + 1
		return c


class Solution:

	def getGray(self, n):
		sum = 0
		b = bin(n)
		b = b.replace('0b', '')
		l = [int(i) for i in b]
		l1 = []
		l1.append(l[0])
		for i in range(1, len(l)):
			x = l[i] ^ l[i - 1]
			l1.append(x)
		st = ''
		for i in l1:
			st = st + str(i)
		res = int(st, 2)
		return res


class Solution:

	def getGray(self, n):
		na = bin(n)
		narray = na.split('0b')
		ans = ''
		for i in range(len(narray[1]) - 1, 0, -1):
			ans = ans + str(abs(int(narray[1][i]) - int(narray[1][i - 1])))
		ans = ans + str(narray[1][0])
		fans = 0
		for i in range(len(ans)):
			fans = fans + pow(2, i) * int(ans[i])
		return fans


class Solution:

	def getGray(self, n):
		b = bin(n)[2:]
		l = []
		l.append(b[0])
		for i in range(len(b) - 1):
			l.append(str(int(b[i]) ^ int(b[i + 1])))
		return int(''.join(l), 2)


class Solution:

	def getGray(self, n):
		bin = ''
		while n > 0:
			bin = str(n % 2) + bin
			n = n // 2
		if len(bin) == 0:
			bin = '0'
		grey = ''
		for i in range(len(bin) - 1, -1, -1):
			if i != 0:
				if bin[i] == bin[i - 1]:
					grey = '0' + grey
				else:
					grey = '1' + grey
			else:
				grey = bin[i] + grey
		ans = 0
		fac = 1
		for i in range(len(grey) - 1, -1, -1):
			ans += int(grey[i]) * fac
			fac *= 2
		return ans


class Solution:

	def getGray(self, n):
		b = bin(n)
		b = b[2:]
		s = b[0]
		for i in range(1, len(b)):
			if b[i - 1] == b[i]:
				s = s + '0'
			else:
				s = s + '1'
		s = s[::-1]
		r = 0
		i = 0
		for e in s:
			r += int(e) * 2 ** i
			i += 1
		return r


class Solution:

	def getGray(self, n):
		a = bin(n).replace('0b', '')
		b = []
		for i in str(a):
			b.append(i)
		for i in range(0, len(b) - 1):
			if a[i] == a[i + 1]:
				b[i + 1] = '0'
			else:
				b[i + 1] = '1'
		w = ''.join(b)
		return int(w, 2)


class Solution:

	def toBinary(self, n):
		b = []
		while n:
			b.append(n % 2)
			n //= 2
		return b[::-1]

	def toDecimal(self, n):
		m = 0
		for i in n:
			m = m * 2 + i
		return m

	def getGray(self, n):
		if n == 0:
			return 0
		binary = self.toBinary(n)
		x = [binary[0]]
		for i in range(len(binary) - 1):
			x.append(binary[i] ^ binary[i + 1])
		return self.toDecimal(x)


class Solution:

	def getGray(self, n):
		bin1 = bin(n).replace('0b', '')
		lst = [bin1[0]]
		for i in range(len(bin1) - 1):
			res = int(bin1[i]) ^ int(bin1[i + 1])
			lst.append(str(res))
		l = ''.join(lst)
		return int(l, 2)