[closed] Gray Code

Question

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Answer 1

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        int count = 0x01 << n;
        for(int i = 0 ; i < count; ++i) {
            ret.push_back(i ^ (i>>1));
        }
        return ret;
    }
};

Answer 2

vector<int> grayCode(int n) {
    vector<int> r;
    r.push_back(0);
    for(int i = 0; i < n; ++i)
        for(int j = r.size() - 1; j >= 0; --j)
            r.push_back(r[j] | 1 << i);
    return r;
}

Answer 3

A recursive solution in java

public ArrayList<Integer> grayCode(int n) {  
    ArrayList<Integer> resultList = new ArrayList<Integer>();
    if (n <= 1) {
        resultList.add(0);
        if (n == 1) resultList.add(1);
        return resultList;
    }

    ArrayList<Integer> prevList = grayCode(n - 1);
    int highest_bit = 1 << (n - 1);
    for (int i = prevList.size() - 1; i >= 0; i--) {
        resultList.add(prevList.get(i) + highest_bit);
    }

    prevList.addAll(resultList);
    return prevList;
}

Answer 4

class Solution 
{
public:
  vector<int> grayCode(int n) 
 {
  // Start typing your C/C++ solution below
  // DO NOT write int main() function
  vector<int> r;
  int num = 1 << n;
  for(int i=0;i<num;i++)
  {
    r.push_back(i ^ (i>>1));
  }
  return r;
 } 
};

Answer 5

class Solution {
public:
vector<int> grayCode(int n) {
  vector<int> vec;
    int loop = (1<<n);
    for (int i = 0; i < loop; i++)
        vec.push_back(i^(i>>1));
    return vec;
}
};

Answer 6

vector<int> grayCode(int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
   vector<int> ret;
   ret.push_back(0);
   int mask = pow(2, n)-1;
   int visit = (int(pow(2, n)) & mask), i=0, cur = 1, x = 0;
   while(i < mask)
   {
        while(( (visit >> (cur-1)) & 1 ) != 0)
        {
            cur ++;
        }

       x = (x ^ (1 << (cur-1))) & mask;    // make cur pos in x as opposite, 0->1, 1->0
       visit = visit & ~((1 << cur) - 1);  // make the bit to the left of cur as 0, which is not visited
       visit = visit | (1 << (cur-1));     // make cur as 1, which is visited
       ret.push_back(x);
       cur = 1;                            // cur back to 1, ready to change from the lowest bit

       i++;      
   }
   return ret;
}

Answer 7

An alternative solution using bit operations

public class Solution {       
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> ans=new ArrayList<Integer>();
        for (int i=0;i<1<<n;i++)
            ans.add(0);
            for (int i=0;i<n;i++){
                for (int j=0;j<ans.size();j++){
                    int exp=0^((j>>i)&1) ^(j>>(i+1) &1);
                    ans.set(j, ans.get(j)+(1<<i)*exp);
                }
            }        
        return ans;
    }
}

Answer 8


//recursive approach in C++
std::vector<int> v;
std::vector<int> grayCode(int n) {
    v.clear();
    if (n >= 0) v.push_back(0);
    if (n >= 1) v.push_back(1);
    int k = 1;
    while (k < n) {
        unsigned int highestBit = 1 << k;
        int sz = v.size();
        for (int i = sz-1; i >= 0; --i) {
            v.push_back(v[i]|highestBit);
        }
        ++k;
    }       
    return v;
}

[closed] Gray Code

The question has been closed for the following reason "bulk close" by 1337c0d3r 25 Oct '13, 06:41

Follow this question

Welcome to LeetCode

Related questions