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]

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;
}