This is basically about bit operator, specifically XOR


  • 0
    T

    the idea I used is basically flipping the bit at such a location: the location is the same position of the FIRST bit that changed as you increment to a new number , i.e. the first bit that changed when u go from i-1 to i.

    interestingly, the expression i^(i-1) gives u 0111 , for example if u go from 3 to 4 in a 4-bit number (0011 to 0100). then if u shift it one bit to the right, u get 0011, and if u XOR these 2 numbers , u get the 0100 that you wanted. then u just need to flip the last number, on the bit corresponding to the "1" bit above, u get the next number in the required sequence.

    public class Solution {
    public List<Integer> grayCode(int n) {
        int x = 0;
        List<Integer> result = new ArrayList<Integer>();
        result.add(x);
        for(int i=1;i<Math.pow(2,n);i++) {
            int mask = i ^ (i -1 );
            x = x^ ( mask ^ (mask >>1));
            result.add(x);
        }
        
        return result;
    }
    

    }


Log in to reply
 

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