Gray Code - Practice Coding Problems

Gray Code - Problem

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

Every integer is in the inclusive range [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.

Input & Output

Example 1 — Basic Case (n=2)

$ Input: n = 2

› Output: [0,1,3,2]

💡 Note: Binary: [00,01,11,10]. Each adjacent pair differs by one bit: 00→01 (bit 0), 01→11 (bit 1), 11→10 (bit 0), 10→00 (bit 1, wraps around).

Example 2 — Minimum Case (n=1)

$ Input: n = 1

› Output: [0,1]

💡 Note: Binary: [0,1]. Only two 1-bit numbers: 0→1 differs by bit 0, and 1→0 wraps around differing by bit 0.

Example 3 — Edge Case (n=0)

$ Input: n = 0

› Output: [0]

💡 Note: Only one 0-bit number exists: 0. Single element trivially satisfies Gray code properties.

Constraints

0 ≤ n ≤ 16
Answer is guaranteed to fit in a 32-bit integer

Visualization

Tap to expand

Understanding the Visualization

Input

n = 2 (want 2-bit Gray code)

Process

Build sequence where adjacent numbers differ by one bit

Output

[0,1,3,2] with binary [00,01,11,10]

Key Takeaway

🎯 Key Insight: Gray codes follow a recursive doubling pattern with bit manipulation

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that Gray codes follow a recursive pattern where G(n) = [G(n-1), reverse(G(n-1)) + 2^(n-1)]. Best approach is iterative bit manipulation to avoid recursion overhead. Time: O(2^n), Space: O(2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Iterative Bit Manipulation	O(2^n)	O(2^n)	Build sequence iteratively without recursion using bit operations
Mathematical Pattern (Recursive)	O(2^n)	O(2^n)	Use the mathematical property that G(n) can be built from G(n-1)
Brute Force Backtracking	O(2^n × n)	O(2^n)	Try all possible sequences and backtrack when stuck

Iterative Bit Manipulation — Algorithm Steps

Start with [0]
For each bit position i from 0 to n-1
Append reverse of current sequence
Set bit i in the new elements

Visualization

Tap to expand

Step-by-Step Walkthrough

i=0

Start [0], add [1] → [0,1]

i=1

Have [0,1], add [3,2] → [0,1,3,2]

Pattern

Each step doubles by adding reverse with MSB

Code -

solution.c — C

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

int* solution(int n, int* returnSize) {
    *returnSize = 1 << n; // 2^n
    int* result = (int*)malloc((*returnSize) * sizeof(int));
    result[0] = 0;
    int currentSize = 1;
    
    for (int i = 0; i < n; i++) {
        // Add reverse sequence with i-th bit set
        for (int j = currentSize - 1; j >= 0; j--) {
            result[currentSize + (currentSize - 1 - j)] = (1 << i) | result[j];
        }
        currentSize *= 2;
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int returnSize;
    int* result = solution(n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Must generate all 2^n numbers, each step doubles sequence size

⚠ Quadratic Growth

Space Complexity

O(2^n)

Store the result array of size 2^n

⚠ Quadratic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Iterative Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler