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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment