O(2^n) Time complexity && O(1) Space with my explanation


  • 0
    H

    The obvious way when I first saw this question is using backtracking/brute-force. By Grey Code definition,

    1. from 0, I try to modify each bits from very right to left.
    2. after modify this bits, If there is no such num in my hashSet, put it into hashSet and also result list, if there is such num in my hashSet, move to higher bits and repeat step 2, until get 2^n numbers

    I assume n bits must have a way to transfer 0-2^n-1 to gray code. The following is proof.
    I use induction to proof this. So we proof If k bits can get 2^k gray code, then k+1 bits can get 2^(k+1) gray code. For the k + 1 bits gray codes, the first 2^k gray codes' highest bit is "0", with the same order of k bits's gray code. the second 2^k gray codes' highest bit is "1" with the symmetrical order of k bits' gray code. Such, we get the 2^(k+1) gray code.
    For this solution, time complexity is n*2^n, 2^n numbers and to get each numbers, at most n bits to modify.

    It is far away from optimization. So I try another way.

    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> res = new ArrayList<Integer>();
            for(int i = 0; i < (1 << n); i++) {
                res.add(i ^ (i >> 1));
            }
            return res;
        }
    }
    

    i ^ (i >> 1) means for i-th gray code, we can get it by the following way:

    1. invert bits if higher bit is "1"
    2. keep the original bit if higher bit is "0"

    Why? Generally because we get our gray code by "recursive symmetry with 2^k".
    Let we take 6-th gray code as example. 6 is "110", The first bits "1" means 6-th gray code is on the second half part, in this part, second bit "1" shows 6-th gray code is on the second half part of second half part, third bit "0" shows the gray code is one the first half of the second half of the second part. By inverting, we can get symmetric position of 6-th, which is "001". Considering the 6-th is in the second part, also add 1 to the highest bit of "001", which leads to our 6-th gray code "101"


Log in to reply
 

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