In this Leetcode Gray Code problem solution 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.
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; }