Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Gray Code

Gray Code

Master this topic with zero to advance depth.

Gray Code

An n-bit gray code sequence is a sequence of 2n2^n integers where:

  • Every integer is in the inclusive range [0,2n−1][0, 2^n - 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,
  • 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.

Medium

Examples

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

00, 01, 11, 10 is a valid Gray code sequence.

Approach 1

Level I: Brute Force (Backtracking)

Intuition

Generate the sequence by exploring all possible next numbers that differ by exactly one bit. Maintain a visited set to ensure uniqueness.

Thought Process

  1. Start with 0.
  2. Try flipping each of the nn bits.
  3. If the result is not visited, move to it and recurse.
  4. If all bits visited, return the sequence.

Pattern: State Space Search

⏱ O(2^n) - We generate $2^n$ numbers exactly once.💾 O(2^n) - To store the result and visited set.
java
import java.util.*;

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        backtrack(n, res, visited);
        return res;
    }
    
    private boolean backtrack(int n, List<Integer> res, Set<Integer> visited) {
        if (res.size() == (1 << n)) return true;
        int curr = res.get(res.size() - 1);
        for (int i = 0; i < n; i++) {
            int next = curr ^ (1 << i);
            if (!visited.contains(next)) {
                visited.add(next);
                res.add(next);
                if (backtrack(n, res, visited)) return true;
                res.remove(res.size() - 1);
                visited.remove(next);
            }
        }
        return false;
    }
}
Approach 2

Level II: Reflected Construction (Iterative)

Intuition

Gray code for nn bits can be built from the Gray code for n−1n-1 bits by reflecting the sequence and adding a leading 1 (bit n−1n-1) to the reflected part.

⏱ $O(2^N)$💾 $O(1)$ (excluding output)
java
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        for (int i = 0; i < n; i++) {
            int size = res.size();
            for (int k = size - 1; k >= 0; k--) {
                res.add(res.get(k) | (1 << i));
            }
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Bit Manipulation Formula)

Intuition

The ii-th number in the Gray code sequence can be generated using the formula G(i)=i⊕(i/2)G(i) = i \oplus (i / 2). This formula ensures that adjacent numbers differ by exactly one bit because shifting and XORing cancels out bits that change in a ripple carry but leaves the most significant changing bit.

Thought Process

  1. The total number of elements is 2n2^n.
  2. For each index ii from 0 to 2n−12^n - 1:
    • Calculate i ^ (i >> 1).
  3. Add to result list and return.

Pattern: Formula-based Generation

⏱ O(2^n) - Constant time per element.💾 O(1) - Excluding the output storage.

Detailed Dry Run

n = 2

  • i=0: 0 ^ (0>>1) = 0 ^ 0 = 0 (00)
  • i=1: 1 ^ (1>>1) = 1 ^ 0 = 1 (01)
  • i=2: 2 ^ (2>>1) = 2 ^ 1 = 3 (11)
  • i=3: 3 ^ (3>>1) = 3 ^ 1 = 2 (10) Result: [0, 1, 3, 2]
java
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}
← Previous QuestionCount Triplets That Can Form Two Arrays of Equal XOR
Next Question →Repeated DNA Sequences