89. Gray Code - Solution & Explanation

The problem

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

Every integer is in the inclusive range [0, 2ⁿ - 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

Approach overview

Problem Overview: Gray code is a sequence of 2^n integers where each consecutive value differs by exactly one bit. Given n, generate any valid sequence of n-bit Gray codes starting from 0.

Approach 1: Bit Manipulation Formula (O(2^n) time, O(1) extra space)

The most direct solution uses a known property of Gray codes: the i-th Gray code equals i ^ (i >> 1). Iterate from 0 to 2^n - 1, compute the value using a bitwise XOR between the number and itself shifted right by one bit, and append the result. The XOR operation ensures only one bit changes between consecutive values. This approach relies on bit manipulation and simple iteration, producing the sequence in linear time relative to the output size. Since we only compute values on the fly, the algorithm uses constant auxiliary space besides the output list.

Approach 2: Recursive Gray Code Generation (O(2^n) time, O(2^n) space)

Gray codes follow a reflective pattern. For n bits, first generate the sequence for n-1 bits. Keep that list as the first half. Then reverse the list and prefix each value with a leading 1 (equivalent to adding 1 << (n-1)). Appending this modified reversed sequence creates a valid Gray code order where adjacent numbers differ by one bit. This recursive construction highlights the mathematical structure of Gray codes and naturally fits backtracking or recursive thinking. The main cost comes from storing and expanding the list at each level.

Example pattern for n = 3: start with [0]. For n = 1 → [0,1]. For n = 2 → [0,1,3,2]. For n = 3, reflect the previous sequence and add the leading bit: [0,1,3,2,6,7,5,4]. Each boundary between halves still differs by exactly one bit.

Both approaches rely on properties of binary representation and concepts from math. The sequence length is always 2^n, so any correct algorithm must at least generate that many values.

Recommended for interviews: The bit manipulation formula i ^ (i >> 1) is the expected answer. It shows strong understanding of binary operations and generates the sequence with minimal logic. The recursive reflection approach demonstrates how Gray codes are constructed mathematically, which helps when interviewers want to test reasoning rather than memorization.

Approach 1: Using Bit Manipulation

Gray code can be generated using a simple bit manipulation technique. For a given integer k, the corresponding Gray code is obtained by XORing k with (k >> 1). This technique ensures that each step in changing numbers results in transitioning only one bit.

Python

def gray_code(n):
    size = 1 << n
    for i in range(size):
        gray = i ^ (i >> 1)
        print(gray, end=' ')

n = 2
gray_code(n)

Java

public class GrayCode {
    public static void main(String[] args) {
        int n = 2;
        grayCode(n);
    }

    public static void grayCode(int n) {
        int size = (int) Math.pow(2, n);
        for (int i = 0; i < size; i++) {
            int gray = i ^ (i >> 1);
            System.out.print(gray + " ");
        }
    }
}

C++

#include <iostream>
#include <cmath>

void grayCode(int n) {
    int size = 1 << n;
    for (int i = 0; i < size; i++) {
        int gray = i ^ (i >> 1);
        std::cout << gray << " ";
    }
}

int main() {
    int n = 2;
    grayCode(n);
    return 0;
}

JavaScript

function grayCode(n) {
    const size = 1 << n;
    const result = [];
    for (let i = 0; i < size; i++) {
        result.push(i ^ (i >> 1));
    }
    console.log(result.join(' '));
}

grayCode(2);

#include <stdio.h>
#include <math.h>

void grayCode(int n) {
    int size = pow(2, n);
    for (int i = 0; i < size; i++) {
        int gray = i ^ (i >> 1);
        printf("%d ", gray);
    }
}

int main() {
    int n = 2;
    grayCode(n);
    return 0;
}

using System;

class GrayCode {
    static void Main() {
        int n = 2;
        GrayCodeSequence(n);
    }

    static void GrayCodeSequence(int n) {
        int size = 1 << n;
        for (int i = 0; i < size; i++) {
            int gray = i ^ (i >> 1);
            Console.Write(gray + " ");
        }
    }
}

This Python script computes Gray codes for the range 0 to 2ⁿ - 1 using bit manipulation: i ^ (i >> 1). Each result is printed immediately.

Complexity

Time complexity: O(2ⁿ).
Space complexity: O(1).

Try this approach in the editor

Approach 2: Recursive Gray Code Generation

The Gray code can be recursively generated by reflecting the existing sequence. Start with a base case of n=1: [0,1]. For each subsequent n, reflect the current list, prepend a bit to the reflected part, and concatenate the results: if G_n-1 = [0, 1], then G_n = [0G_n-1, 1G_n-1].

Python

def gray_code(n):
    if n == 0:
        return [0]
    lower = gray_code(n - 1)
    return lower + [(1 << (n - 1)) | i for i in reversed(lower)]

n = 2
result = gray_code(n)
print(' '.join(map(str, result)))

Java

import java.util.*;

public class GrayCode {
    public static List<Integer> grayCode(int n) {
        if (n == 0) return Arrays.asList(0);
        List<Integer> lower = grayCode(n - 1);
        List<Integer> result = new ArrayList<>(lower);
        int size = lower.size();
        for (int i = size - 1; i >= 0; i--) {
            result.add(lower.get(i) | (1 << (n - 1)));
        }
        return result;
    }
    
    public static void main(String[] args) {
        int n = 2;
        List<Integer> gray = grayCode(n);
        for (int code : gray) {
            System.out.print(code + " ");
        }
    }
}

C++

#include <iostream>
#include <vector>

std::vector<int> grayCode(int n) {
    if (n == 0) return {0};
    std::vector<int> lower = grayCode(n - 1);
    std::vector<int> result = lower;
    int size = lower.size();
    for (int i = size - 1; i >= 0; i--) {
        result.push_back(lower[i] | (1 << (n - 1)));
    }
    return result;
}

int main() {
    int n = 2;
    std::vector<int> gray = grayCode(n);
    for (int code : gray) {
        std::cout << code << " ";
    }
    return 0;
}

JavaScript

function grayCode(n) {
    if (n === 0) return [0];
    const lower = grayCode(n - 1);
    const addOn = 1 << (n - 1);
    return lower.concat(lower.map(x => x | addOn).reverse());
}

const n = 2;
console.log(grayCode(n).join(' '));

#include <stdio.h>
#include <stdlib.h>

void generate(int n, int* result) {
    if (n == 0) {
        result[0] = 0;
        return;
    }

    generate(n-1, result);
    int size = 1 << (n-1);
    for (int i = 0; i < size; i++) {
        result[size + i] = result[size - 1 - i] | (1 << (n-1));
    }
}

int* grayCode(int n, int* returnSize) {
    *returnSize = 1 << n;
    int* result = (int*)malloc(sizeof(int) * (*returnSize));
    generate(n, result);
    return result;
}

int main() {
    int n = 2;
    int returnSize;
    int* gray = grayCode(n, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", gray[i]);
    }
    free(gray);
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    static List<int> GrayCode(int n) {
        if (n == 0) return new List<int> { 0 };
        List<int> lower = GrayCode(n - 1);
        List<int> result = new List<int>(lower);
        int addOn = 1 << (n - 1);
        for (int i = lower.Count - 1; i >= 0; i--) {
            result.Add(lower[i] | addOn);
        }
        return result;
    }

    static void Main() {
        int n = 2;
        List<int> gray = GrayCode(n);
        Console.WriteLine(string.Join(" ", gray));
    }
}

This Python solution recursively computes Gray codes by reflecting the previously computed sequence and appending bit-changed reflections.

Complexity

Time complexity: O(2ⁿ).
Space complexity: O(2ⁿ), storing outcomes in a list with recursive data expansion.

Try this approach in the editor

Approach 3: Binary to Gray Code Conversion

Gray code is a type of encoding method that we often encounter in engineering. Its basic feature is that only one bit of binary number is different between any two adjacent codes.

The rule for converting binary code to binary Gray code is to keep the highest bit of the binary code as the highest bit of the Gray code, and the second highest bit of the Gray code is the XOR of the highest bit and the second highest bit of the binary code. The calculation of the remaining bits of the Gray code is similar to the second highest bit.

Assume that a binary number is represented as B_{n-1}B_{n-2}...B_2B_1B_0, and its Gray code is represented as G_{n-1}G_{n-2}...G_2G_1G_0. The highest bit is retained, so G_{n-1} = B_{n-1}; and the other bits G_i = B_{i+1} \oplus B_{i}, where i=0,1,2..,n-2.

Therefore, for an integer x, we can use the function gray(x) to get its Gray code:

int gray(x) {
    return x ^ (x >> 1);
}

We directly map the integers [0,..2^n - 1] to the corresponding Gray codes to get the answer array.

The time complexity is O(2^n), where n is the integer given in the problem. Ignoring the space consumption of the answer, the space complexity is O(1).

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

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Bit Manipulation	Time complexity: O(2ⁿ). Space complexity: O(1).
Recursive Gray Code Generation	Time complexity: O(2ⁿ). Space complexity: O(2ⁿ), storing outcomes in a list with recursive data expansion.
Binary to Gray Code Conversion	–

Complexity analysis

Approach	Time	Space	When to Use
Bit Manipulation Formula (i ^ (i >> 1))	O(2^n)	O(1) auxiliary	Best for interviews and production. Simple iteration with minimal logic.
Recursive Reflection Construction	O(2^n)	O(2^n)	Useful to understand Gray code structure or when explaining the mathematical construction.

Frequently asked questions

Is Gray Code easy or hard?

Gray Code is generally considered a medium difficulty problem. The implementation becomes very simple once you know the formula i ^ (i >> 1), but deriving or recognizing that property requires understanding of binary patterns and bit manipulation.

Gray Code Python/Java solution

In Python or Java, loop from 0 to (1 << n) - 1 and compute gray = i ^ (i >> 1). Append each result to a list or array. The implementation is only a few lines and runs in O(2^n) time.

How to solve Gray Code in O(2^n)?

Iterate through integers from 0 to (1 << n) - 1 and compute each value as i ^ (i >> 1). The XOR between the number and its right-shifted version guarantees that consecutive values differ by exactly one bit. Append each result to the output list.

What is the best approach for Gray Code?

The most efficient approach uses the bit manipulation formula i ^ (i >> 1). Iterate from 0 to 2^n - 1 and compute each Gray code directly using XOR and a right shift. This runs in O(2^n) time with O(1) auxiliary space and is the approach most interviewers expect.

Is Gray Code asked at Google/Amazon/Meta?

Gray Code appears in interviews that test bit manipulation and binary representation. Variations of the problem have been reported in interviews at companies like Amazon, Google, and other large tech firms, especially for roles that emphasize low-level reasoning.

What data structure is used in Gray Code?

The core solution mainly relies on bit manipulation operations such as XOR and bit shifting. The generated sequence is typically stored in a dynamic array or list since the output size is 2^n.

What is the time complexity of Gray Code?

Any algorithm must output 2^n numbers, so the time complexity is O(2^n). The optimal bit manipulation solution generates each value with a constant-time operation, keeping the overall complexity proportional to the sequence size.

Gray Code solution and explanation

The problem

Approach overview

Approach 1: Using Bit Manipulation

Approach 2: Recursive Gray Code Generation

Approach 3: Binary to Gray Code Conversion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Gray Code solution and explanation

The problem

Approach overview

Approach 1: Using Bit Manipulation

Approach 2: Recursive Gray Code Generation

Approach 3: Binary to Gray Code Conversion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems