What is the best solution for Gray Code problem? No extra space used and no recursion?


  • 60
    S

    I have a solution here which takes O(1) on space and no recursion used. Is this the best possible solution? (I combined the base cases in the loop as mike3 does. Thanks mike3!)

    vector<int> grayCode(int n) 
    {         
        vector<int> result(1, 0);        
        for (int i = 0; i < n; i++) {
            int curCount = result.size();
            // push back all element in result in reverse order
            while (curCount) {
                curCount--;
                int curNum = result[curCount];
                curNum += (1<<i);
                result.push_back(curNum);
            } 
        }
        return result;
    }

  • 108
    M

    Not sure why you have the if(n==1) in there. Seems like that would just skip over the for loop and return at the end. Anyways, here's my Java version. We apparently have the same algorithm.

    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        arr.add(0);
        for(int i=0;i<n;i++){
            int inc = 1<<i;
            for(int j=arr.size()-1;j>=0;j--){
                arr.add(arr.get(j)+inc);
            }
        }
        return arr;
    }
    

    }


  • 0
    S

    Thanks for your comments. We have same algorithm but apparently your codes are more readable. I need to combine base cases inside the loop as you did.


  • 4
    I

    here is a simple python code for this problem, actually I just skipped the Gray Code generation part...

    def grayCode(self, n):
        if n == 0: return [0]
        result = [0, 1]
        for i in xrange(1, n):
            result += [(x + 2**i) for x in reversed(result)]
        return result

  • 0
    C

    If you take a second look you will notice that n=0 isn't a corner case, set result = [0] and loop start from 0


  • 18
    M
    class Solution:
    # @return a list of integers
    def grayCode(self, n):
        num = 2**n
        return map(lambda x:(x>>1)^x,[x for x in range(num)])
    

    after I check the wikipedia what's the Gray Code, then, It's easy.


  • 0
    S

    Yes, it is a way to generate. Have you tried a recursive way? Even though someone doesn't know Gray Code is like that, it is possible to solve it.


  • 0
    A
    This post is deleted!

  • 1
    S

    Thanks for your post. However it would be better to post as answer with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 2
    Z

    if n=2 we got [00,01,11,10], the next number will be 110 which add an 1 in front of last element 10. we can generate other element when n=3.
    110:don't change any bit of 110, i.e. 110^00
    111:change the last bit of 110, i.e. 110^01
    101:change the last two bits of 110, i.e. 110^11
    101:change the second bits of 110, i.e. 110^10
    so it is easy to write such code below:

    class Solution:
    # @return a list of integers
    def grayCode(self, n):
        ret=[0]
        for i in range(n):
            start_num=ret[-1]|(1<<i)
            ret.extend([start_num^elem for elem in ret])
        return ret

  • 15
    D

    Counting from 0, when we generate v[i] from v[i-1], we just need to change bit where the rightmost bit 1 locates in i. For example, [00, 01, 11, 10], when we generate 11(2nd) from 01(1st), we just xor 01 with 10(rightmost bit 1 of 2); when we generate 10(3th) from 11(2nd), we just xor 11 with 01(rightmost bit 1 of 3). Here I use "i&-i" to get the rightmost bit 1 of i.

    vector<int> grayCode(int n) {
        vector<int> v(1,0);
        for (int i=1;i<(1<<n);i++) v.push_back(v[i-1]^(i&-i));
        return v;
    }
    

  • 0
    Z

    I don't get how does this work: (x>>1)^x? Could you please explain more? Thanks!!


  • 0
    M

    http://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code
    I said above, the wikipedia helps me. May it will help you also.


  • 0
    N
    vector<int> grayCode(int n) {
        
        int m = pow(2,n); // total numbers
    
        vector<int> res;
    
        // http://en.wikipedia.org/wiki/Gray_code
        for (int i = 0;i<m;i++)
        {
            int temp = (i>>1)^i; // generating the gray code
            res.push_back(temp);
        }
        return res;
    }
    

  • 2
    L

    Same idea here ...
    Our answers should be the best...

    class Solution {
    public:
        vector<int> grayCode(int n) {
            
            vector<int> v={0};
            int i,j,bit=1;
            for(i=0;i<n;i++){
                for(j=v.size()-1;j>=0;j--){
                    v.push_back(bit | v[j]);
                }
                bit <<= 1;
            }
            return v;
        }
    };

  • 4
    C

    A different way of solving this problem. Not smart, but a different idea

    	//try to generate all possible code by 0 1-> 0+0 0+1 1+1 1+0 ->...
    //add 0 at begin forward the array such as 0 1 -> 00 01
    //add 1 at begin reverse the array such as 0 1 -> 11 10
    public List<Integer> grayCode(int n) {
    	List<Integer> outlist = new ArrayList<Integer>();
    	if(n == 0) {
    		outlist.add(0);
    		return outlist;
    	}
    	
    	List<String> list = new ArrayList<String>();
    	list.add("0");
    	list.add("1");
    	
    	for(int i = 0; i < n - 1; i++) {
    		List<String> tlist = new ArrayList<String>();
    		int listLen =  list.size();
    		for(int j = 0; j < listLen; j++) {
    			tlist.add("0" + list.get(j));
    		}
    		for(int j = 0; j < listLen; j++) {
    			tlist.add("1" + list.get(list.size() - 1 - j));
    		}
    		list = tlist;
    	}
    	
    	for(String s : list) {
    		outlist.add(Integer.valueOf(s,2));
    	}
    	return outlist;
    }

  • 0
    B

    This is brilliant!


  • 0
    X

    I also come up with a similar algorithm. But yours is more succinct. Thanks!


  • 0
    B
    class Solution:
    # @return a list of integers
    def grayCode(self, n):
        if n==0:
            return [0]
        result=[]
        result.append(0)
        result.append(1)
        
        cur=2
        
        while cur<=n:
            i=(1<<(cur-1))-1
            j=1<<(cur-1)
            while i>=0:
               result.append(result[i]+j)
               i-=1
            cur+=1
            
        return result
    

    the same idea. copy reversely and add 1 to the end of each of it


  • 1
    W

    more short codes, use i ^ (i / 2)

    class Solution {
    public:
        vector<int> grayCode(int n) {
            vector<int> ret = {0};
            int nums = pow(2, n);
            for (int i = 1; i < nums; ++i) ret.push_back(i ^ (i / 2));
            return ret;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.