[solution] 10 lines c code solution run in 2ms


  • 1
    I
    int *grayCode(int n, int *outputSize) {
    *outputSize = 1 << n;
    int *res = (int *)malloc(sizeof(int) * (*outputSize));
    
    res[0] = 0; 
    for(int i = 1; i < *outputSize; i++){
    	res[i] = res[i - 1] ^ (i & (~i + 1));
    }
    return res;
    }
    

    any problems?


  • 0
    S

    can you elaborate on this expression (i & (~i + 1)) please?
    it seems to magically generate 1,2,1,4,1,2,1,8,1,2,1..etc, but how did you come to this?


  • 0
    R

    I got this wiki solution written in c.but it seems has nothing to do with backtracking

    int* grayCode(int n, int* returnSize) {
    	*returnSize= 1<<n; 
    	int *ret=malloc(sizeof(int)*(*returnSize));
    	if(NULL==ret)
    		exit(-1);
    
    	ret[0]=0;
    	int i=1;
    	for(;i<(*returnSize);++i)
    		ret[i]=i^(i>>1);
    	return ret;
    }

Log in to reply
 

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