I. Inductive Construction

Construction Process

• A 1-bit Gray Code has exactly two elements: [0, 1].

• Let G(n-1) be the (n-1)-bit Gray Code sequence of length c' = 2^{N-1}.
• When constructing an n-bit Gray Code from an (n-1)-bit sequence:
  • The total number of codes doubles from 2^{N-1} to 2^N.

To construct G(n) from G(n-1):

1. First half:
   • Take all codes from G(n−1) and prefix a 0 to each of them.
   • This gives the first c' elements of G(n) and preserves the original order.
   • e.g.
     • From G(2) = [00, 01, 11, 10],
     • prefixing 0 → [000, 001, 011, 010]
2. Second half:
   • Take all codes from G(n−1) in reverse order, and prefix a 1 to each.
   • This ensures that adjacent codes across the midpoint still differ by only one bit.
   • e.g.
     • Reverse of G(2) = [10, 11, 01, 00]
     • Prefixing 1 → [110, 111, 101, 100]

3. Finally, concatenate the two halves:

   G(3) = [000, 001, 011, 010, 110, 111, 101, 100]

   Solution

   class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> grayCode = new ArrayList<>();
        grayCode.add(0);
   
        for (int i = 0; i < n; i++) {
            int currentSize = grayCode.size();
            for (int j = currentSize - 1; j >= 0; j--) {
                grayCode.add(grayCode.get(j) | (1 << i));
            }
        }
        return grayCode;
    }
   }
   

Time Complexity: O(2^N)
- Iteration 0: 1 operation
- Iteration 1: 2 operations
- Iteration 2: 4 operations
- ...

- Total Operations: 1 + 2 + 4 + ... + 2^{N-1} = 2^N - 1

Space Complexity: O(2^N)
- The only data structure used is the grayCode list, which ultimately holds all 2^N elements.
- Each element is an integer, so the space used is proportional to the number of entries.

II. General Formula

Convert Binary Code to Gray Code

Gray Code:  000, 001, 011, 010, 110, 111, 101, 100, ...
Decimal:     0    1    2    3    4    5    6    7,  ...
Binary:     000, 001, 010, 011, 100, 101, 110, 111, ...

For example, we want to compute the Gray Code for decimal 5.

• Step 1: Convert the decimal to binary
  • 5 in binary = 0101
  • We label each bit of this binary number as b3 b2 b1 b0, from most significant to least significant bit.

  • 
    b = 0   1   0   1
        b3  b2  b1  b0
    

• Step 2: To compute the corresponding Gray Code bits g3 g2 g1 g0, we use the rule:
  • The most significant bit of the Gray Code (g3) is the same as the most significant bit of the binary code (b3).
  • Every subsequent Gray Code bit gᵢ is computed as the XOR (^) of bᵢ and bᵢ₊₁:
  • Applying this to our example b = 0101:

        
    b = 0    1    0    1
        b3   b2   b1   b0
          \⊕/  \⊕/  \⊕/
    g = g3 g2  g1   g0
        0  1    1    1  → Gray Code = 0111
    

This procedure is formalized by the following bitwise expression: Gray Code can be derived directly from binary numbers using the formula: Gray(i)= i ⊕ (i >> 1) i.e.,

gray = i ^ (i >> 1);

Algorithm Logic

We enumerate all n-bit binary numbers from 0 to 2^N - 1, and convert each of them into its corresponding Gray Code.

Solution

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> grayCode = new ArrayList<>();

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

Time Complexity: O(2^N)
Space Complexity: O(2^N)