C++_O(2^n)_Accepted_with brief explanation


  • 0
    • For me, I did not have any background in CS or EE, so I just use method mentioned in https://discuss.leetcode.com/topic/1011/what-is-the-best-solution-for-gray-code-problem-no-extra-space-used-and-no-recursion/2 Thanks a lot!

    • The logic should be like this. Each time we could only change 1 digit in our previous number. In order for clear explanation, I will n = 3. First, let's add 000 in to our res, now we have 1 number. Next step is adding digit 1 to 000. We add 1 from the last number of our res and last digit of that number. so we put 001 in to res.

    • Now we have res = [000, 001]. The next step is add 1 in to the second digit of each number, but we should notice that if we first add 1 to 000 and get 010 and push it back to res, we will find that 001 and 010 have 2 different digits. So we first add 1 to 001 and then add 1 to 000, we now get res = [000, 001, 011, 010]. This step secures our result is correct, because for the 011, it is derived from 001 , so there will be only 1 different digit, for 010, after 000 add 1 to its second digit, the first and second digits are the same as the one derived from 001, so the new one will also be 1 digit different from previous one in res vector.

    • Then add 1 to the first digit and use above algorithm. res = [000,001,011,010,110,111,101,100].
    class Solution {
    public:
    vector<int> grayCode(int n) {
        vector<int> res(1,0);
        for(int i = 0; i < n; i++){
            int k = res.size();
            while(k > 0){
                k--;
                int tmp = res[k] + (1 << i);
                res.push_back(tmp);
            }
        }
        return res;
    }
    };

Log in to reply
 

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