# [LeetCode 89. Gray Code ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3799/)
### Daily challenge Jul 1, 2021 (MEDIAN)

>An **n-bit gray code sequence** is a sequence of 2^n^ integers where:
>
>* Every integer is in the inclusive range [0, 2n - 1],
>* The first integer is `0`,
>* An integer appears no more than once in the sequence,
>* The binary representation of every pair of **adjacent** integers **`differs by exactly one bit`**, and
>* The binary representation of the first and last integers differs by exactly one bit.
>
>Given an integer n, return any valid n-bit gray code sequence.

:::info
**Example 1:**
**Input:** n = 2
**Output:** [0,1,3,2]
**Explanation:**
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit

[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit
:::

:::info
**Example 2:**
**Input:** n = 1
**Output:** [0,1]
:::

:::warning
**Constraints:**
* 1 <= n <= 16
:::

---

### Approach 1 : OR Gate :book:
**`4 ms ( 95.41% )`** **`O()`**

透過觀察，可以發現 `Gray Code` 具有特別的 **`鏡射排列`**。
新增的 `n-bit` 可由 `(n-1)-bit` 鏡射而成，差別只在 `highest bit`。



// VERSION 1 //
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int > ans;
        ans.push_back(0);
        
        int adder = 1;
        
        for(int i=1; i<=n; i++){
            for(int j=0; j<adder; j++){
                ans.push_back(ans[adder - 1 - j] | adder);
            }
            adder <<= 1;
        }
        
        return ans;
    }
};

// VERSION 2//
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        
        for(int i=0; i<n; i++){
            int size = ans.size();
            for(int j=size-1; j>=0; j--){
                ans.push_back(ans[j] | 1<<i);
            }
        }
        
        return ans;
    }
};

### Approach 2 : XOR Gate :book:
**`4 ms ( 95.41% )`** **`O()`**


// VERSION 1
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;

        for(int i=0; i < (1<<n); i++){
            ans.push_back(i ^ i>>1);
        }
        
        return ans;
    }
};

[參考資料](https://leetcode.com/problems/gray-code/discuss/245076/4-lines-Elegant-fast-and-easy-understand-Python-solution)

// VERSION 2
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        
        int total = pow(2, n);
        for(int i=1; i<total; i++){
            ans.push_back(ans.back() ^ (i & -i));
        }
        
        return ans;
    }
};