Gray Code

How it works

Reflect the current Gray-code sequence and prefix the reflected half with the next bit. The boundary between the old and new halves differs only in that bit, while adjacency inside each half preserves the earlier one-bit property.

Steps

1. Start with [0].
2. For each bit position, walk the existing sequence backward.
3. Append each visited value with the new bit set.

Complexity

• Time: O(2^n).
• Space: O(2^n) for the returned sequence; O(1) additional workspace.

Things to watch for

• Traverse the old sequence in reverse to preserve adjacency.
• Do not iterate over newly appended values.
• The first and last codes must also differ by one bit.

class Solution:
  def grayCode(self, n: int) -> list[int]:
    ans = [0]

    for i in range(n):
      for j in reversed(range(len(ans))):
        ans.append(ans[j] | 1 << i)

    return ans

class Solution {
 public:
  vector<int> grayCode(int n) {
    vector<int> ans{0};

    for (int i = 0; i < n; ++i)
      for (int j = ans.size() - 1; j >= 0; --j)
        ans.push_back(ans[j] | 1 << i);

    return ans;
  }
};