# Gray Code Problem Solution

Gray Code Problem: An n-bit gray code sequence is a sequence of `2n` integers where:

• Every integer is in the inclusive range `[0, 2n - 1]`,
• The first integer is `0`,
• An integer appears no more than once in the sequence,
• The binary representation of every pair of adjacent integers differs by exactly one bit, and
• The binary representation of the first and last integers differs by exactly one bit.

Given an integer `n`, return any valid n-bit gray code sequence.

Example :

```Input: n = 2
Output: [0,1,3,2]```

## Problem Solution In Python

``````class Solution:
def grayCode(self, n: int) -> List[int]:
ans = []
for i in range(0, 2 ** n):
b = bin(i)[2:]
temp = b[0]
for j in range(1, len(b)):
temp += str(int(b[j - 1]) ^ int(b[j]))
ans.append(temp)

return list(map(lambda x: int(x, 2), ans))
``````

## Problem Solution In Java

``````class Solution {
public List<Integer> grayCode(int n) {
ArrayList<Integer> res = new ArrayList<>();
int num = 1<<n;
for(int i = 0; i < num; i++) {
}
return res;
}
}
``````

## Problem Solution In C++

``````vector<int> grayCode(int n) {
if(n == 0) return {0};
vector<int> ret = {0, 1};

for(int i=2; i<=n; i++)
for(int j=ret.size()-1; j>=0; j--)
ret.push_back(ret[j]+(1<<i-1));

return ret;
}
``````

## Problem Solution In C

``````int* grayCode(int n, int* returnSize) {
*returnSize=1<<n;
unsigned int* pAns=(unsigned int*)malloc(*returnSize*sizeof(unsigned int));
pAns[0]=0;
for (unsigned int i=1;i<*returnSize;i++){
unsigned int temp=i;
for (int j=0;j<n;j++){//xor the last bit which is not zero
if (temp%2!=0){
pAns[i]=pAns[i-1]^(1<<j);
break;
}
temp=temp>>1;
}
}
return pAns;
}``````