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]
Table of Contents
Gray Code Problem Solution
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++) {
res.add((i>>1)^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;
}