1ms Java solution with explaination


  • 0
    S

    The idea is simple. Consider following 2-bit number:
    00
    01
    mirror
    11
    10
    If we don't look at the most significant bit, these numbers are symmetric. Then consider following 3-bit number:
    000
    001
    011
    010
    mirror
    110
    111
    101
    100
    Still, they are symmetric if you dont look at the most significant bit. Then, to compute the number, we only need find its symmetric number and do xor operation with 1 << i, where i is the most significant bit.

    public List<Integer> grayCode(int n) {
            List<Integer> res = new ArrayList<>();
            res.add(0);
            int crt = 0;
            int next = 1;
            for (int i = 1; i <= n; i++) {
                crt = next;
                next <<= 1;
                for (int j = crt - 1; j >= 0; j--) {
                    res.add(crt ^ res.get(j));
                }
            }
            return res;
        }
    '''

Log in to reply
 

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