# Question

Formatted question description: https://leetcode.ca/all/89.html

An n-bit gray code sequence is a sequence of 2n 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.

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


Example 2:

Input: n = 1
Output: [0,1]


Constraints:

• 1 <= n <= 16

# Algorithm

For n=3:

Int    Grey Code    Binary
0  　　  000        000
1  　　  001        001
2   　 　011        010
3   　 　010        011
4   　 　110        100
5   　 　111        101
6   　 　101        110
7   　　 100        111


My idea is using left shifts, and then operate the lowest bit, followed by 0 or 1.

Another idea is to get the highest position directly, and then add all the previous ones to the highest one

• Note that a for loop starts from 0, if it is n, then <<n-1 is enough
• The second for loop must be reversed from list-size-1 to 0.

If it starts from 0, then the list keeps getting new homes, the size keeps increasing, and it loops endlessly.

# Code

• import java.util.ArrayList;
import java.util.List;

public class Gray_Code {

public static void main(String[] args) {
Gray_Code out = new Gray_Code();
Solution_optimize_on_highest_digit s = out.new Solution_optimize_on_highest_digit();

System.out.println(s.grayCode(3)); // output: [0, 1, 3, 2, 6, 7, 5, 4]
}

// 0 => 0,1 => 10,11
public class Solution_optimize_on_highest_digit {
public List<Integer> grayCode(int n) {

List<Integer> list = new ArrayList<Integer>();

for (int i = 1; i <= n; i++) {
int highestBit = 1 << (i - 1);

// @note:@memorize: nice cutoff! no need to use an extra tmpList
for (int j = list.size() - 1; j >= 0; j--) {
}
}

return list;
}
}

public class Solution_on_highest_digit {
public List<Integer> grayCode(int n) {

List<Integer> list = new ArrayList<Integer>();

if (n < 0) {
return list;
}

// init

// @note: append 1 at highest digit position
for (int i = 1; i <= n; i++) {

// int prevLen = list.size();
List<Integer> tmpList = new ArrayList<Integer>(list);
for (int each: list) {
tmpList.add(each + (1 << (i - 1)));
}

list = tmpList;
}

return list;
}
}

public class Solution_on_lowest_digit {
public List<Integer> grayCode(int n) {

List<Integer> list = new ArrayList<Integer>();

if (n == 0) {
return list;
}

for (int i = 2; i <= n; i++) {

List<Integer> allprev = new ArrayList<Integer>(list);

for (int each : allprev) {
each <<= 1;

if (!list.contains(each))
if (!list.contains(each + 1))
}

}

return list;
}
}

}

############

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

• // OJ: https://leetcode.com/problems/gray-code/
// Time: O(2^N)
// Space: O(2^N)
class Solution {
private:
inline int toggle(int n, int i) {
return n ^ (1 << i);
}
int next(int n, unordered_set<int> s) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
ans = toggle(n, i);
if (s.find(ans) == s.end()) break;
}
return ans;
}
public:
vector<int> grayCode(int n) {
unordered_set<int> s{0};
vector<int> ans(pow(2, n), 0);
for (int i = 1; i < ans.size(); ++i) {
s.insert(ans[i] = next(ans[i - 1], s));
}
return ans;
}
};

• class Solution:
def grayCode(self, n: int) -> List[int]:
return [i ^ (i >> 1) for i in range(1 << n)]

############

class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
if n < 1:
return [0]
ans = [0] * (2 ** n)
ans[1] = 1
i = 1
while i < n:
for j in range(0, 2 ** i):
root = (2 ** i)
ans[root + j] = ans[root - j - 1] | mask
i += 1
return ans


• func grayCode(n int) (ans []int) {
for i := 0; i < 1<<n; i++ {
ans = append(ans, i^(i>>1))
}
return
}

• /**
* @param {number} n
* @return {number[]}
*/
var grayCode = function (n) {
const ans = [];
for (let i = 0; i < 1 << n; ++i) {
ans.push(i ^ (i >> 1));
}
return ans;
};