A Clear Idea but it fails, please HELP!


  • 0
    C

    I find a way to generate the gray code.

    if (a,b) in N(N bits) is gray code, that it must have (a ^ b) == (2**i), when i >= 0 and i <= N-1; 
    

    For example:

    Supposed N = 3, a = 0 , b = 1.
    a = 0 = 000, 
    b = 1 = 001,
    a ^ b = 1 == 2**0,
    so (a,b) is a sub-sequence of N-grey code.
    

    And here is what I did:

    public List<Integer> grayCode(int n){
            List<Integer> res = new LinkedList<>();
    
            // Idea:
            // a ^ b % (2^i) == 0
            int len = (int)Math.pow(2,n);
            Set<Integer> set = new HashSet<>();
            int nums = 0;
            int minidx = 0;
            res.add(nums);
            set.add(nums);
            while(set.size() < len){
                for(int i = minidx; i <= len; i++){
                    if(set.contains(i))
                        continue;
                    if(isok(nums ^ i,n)){
                        nums = i;
                        minidx = (minidx + 1 == i)?i:minidx;
                        set.add(i);
                        res.add(i);
                        break;
                    }
                }
            }
            return res;
        }
    
        private boolean isok(int xor,int n){
    
            for(int i = 0; i < n; i++)
                if (xor == Math.pow(2,i))
                    return true;
    
            return false;
        }
    

    The complexity of time is not good, but the idea seems right, doesn't it? It fails in the case whose N is 3. Can someone tell me where is wrong?


Log in to reply
 

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