My C++ solution (7ms & 17lines)


  • 2
    B

    The basic idea is following:
    if n = 3

    000

    001

    011

    010

    100

    101

    111

    110

    Look the columns, it is a repeat of {0, 1, 1, 0}. The first column (from the right) is 0110, the send column is 00111100, every element repeat twice, the third column is 0000111111110000, every element repeat four times.

    class Solution {
    public:
        vector<int> grayCode(int n) {
            int num = 1 << n;
            int sum = 0;
            vector<int> res;
            int t[] = {0, 1, 1, 0};
            for (int i = 0; i < num; ++i) {
                sum = 0;
                for (int j = 0; j < n; ++j) {
                    sum += t[i/(1 << j) % 4] * (1 << j);
                }
                res.push_back(sum);
            }
            return res;
        }
    };

  • 0
    I

    follow your way, the output won't be gray code anymore, even your code accepted by leetcode.


  • 0
    B

    Why? Could you explain it?


  • 0
    D

    The example is incorrect. You may want to correct that.


  • 0
    B

    Yes, you are right, Thank you. The example should be :

    000

    001

    011

    010

    110

    111

    101

    100

    This is what the code outputs.


  • 0
    B

    The example is wrong, I have corrected in my comments. The code is right.


Log in to reply
 

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