Log inSign up
mediumLeetCodeNot Started

Gray Code

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

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, and - The binary representations of the first and last integers differ by exactly one bit.

Given an integer n, return any valid n-bit Gray code sequence.

Example 1 · Example 1: n = 2:

Input: n = 2
Output: [0, 1, 3, 2]
Explanation: 0 (00_2), 1 (01_2), 3 (11_2), 2 (10_2). Every adjacent pair differs by 1 bit, and 2 differs from 0 by 1 bit.

Example 2 · Example 2: n = 1:

Input: n = 1
Output: [0, 1]
Explanation: 0 (0_2) and 1 (1_2) differ by 1 bit.

Constraints:

  • 1 <= n <= 16

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the algebraic foundation of Gray code encoding i ^ (i >> 1).
  • Compare inductive mirror reflection vs direct mathematical generation.
  • Recognize Hamiltonian cycles on hypercube graph topologies.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sequence where consecutive numbers differ by single bit flip.
  • Permutation of [0, 2n - 1] with cyclic Hamming distance 1.
  • Rotary encoder / digital communications pattern.

Algorithmic Decision Tree:

  • Iterate i from 0 to (1 << n) - 1.
  • Append i ^ (i >> 1) to result array.

Connected Patterns:

Power SetCounting BitsSingle Number

1. Backtracking (DFS Search)

Intuition

Maintain a visited set and current path starting with 0. At each step, try flipping bits 0 through n - 1. If the new number hasn't been visited, recurse. Backtrack if dead end is hit.

When to apply: When understanding the graph-theoretic formulation of Gray codes.

Algorithm

  1. Step 1: Initialize visited set with 0, path with [0].
  2. Step 2: Try flipping bit j from 0 to n - 1.
  3. Step 3: If flipped value unvisited, recurse.
  4. Step 4: If path length reaches 2n, solution found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4
5using namespace std;
6
7bool dfs(int n, int total, vector<int>& path, unordered_set<int>& visited) {
8 if ((int)path.size() == total) return true;
9 int curr = path.back();
10 for (int j = 0; j < n; ++j) {
11 int nextVal = curr ^ (1 << j);
12 if (!visited.count(nextVal)) {
13 visited.insert(nextVal);
14 path.push_back(nextVal);
15 if (dfs(n, total, path, visited)) return true;
16 path.pop_back();
17 visited.erase(nextVal);
18 }
19 }
20 return false;
21}
22
23vector<int> grayCodeDFS(int n) {
24 int total = 1 << n;
25 vector<int> path = {0};
26 unordered_set<int> visited = {0};
27 dfs(n, total, path, visited);
28 return path;
29}
30
31int main() {
32 auto res = grayCodeDFS(2);
33 for (int v : res) cout << v << " ";
34 cout << endl; // 0 1 3 2
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(n * 2^n)
  • Space complexity: O(2^n) visited set & recursion stack

2. Mirror Reflection (Induction)

Intuition

Initialize res = [0]. For each step i from 0 to n - 1, observe that mirroring the previous sequence in reverse and adding 1 << i guarantees that adjacent elements only differ by bit i at the mirror boundary.

When to apply: When understanding inductive construction of reflected binary codes.

Algorithm

  1. Step 1: Initialize res = [0].
  2. Step 2: Loop i from 0 to n - 1.
  3. Step 3: len = res.size().
  4. Step 4: Loop j from len - 1 down to 0: res.push_back(res[j] | (1 << i)).
  5. Step 5: Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6vector<int> grayCodeMirror(int n) {
7 vector<int> res = {0};
8 for (int i = 0; i < n; ++i) {
9 int mask = 1 << i;
10 int len = res.size();
11 for (int j = len - 1; j >= 0; --j) {
12 res.push_back(res[j] | mask);
13 }
14 }
15 return res;
16}
17
18int main() {
19 auto res = grayCodeMirror(2);
20 for (int v : res) cout << v << " ";
21 cout << endl; // 0 1 3 2
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(1) auxiliary

3. Direct Binary-to-Gray Code Formula: i ^ (i >> 1)

Intuition

Every binary number i maps to its Gray code counterpart via i ^ (i >> 1). In a simple loop from 0 to (1 << n) - 1, directly append i ^ (i >> 1) to the output.

When to apply: Optimal canonical solution for Gray Code generation.

Algorithm

  1. Step 1: total = 1 << n.
  2. Step 2: Allocate result array of size total.
  3. Step 3: Loop i from 0 to total - 1: res[i] = i ^ (i >> 1).
  4. Step 4: Return res.

Direct Gray Code Generation Trace for n = 2

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
i = 0 (00_2): 0 ^ (0 >> 1) = 0 ^ 0 = 0 (00_2)
Visual state
Values and pointers at this exact step
pointers
S
0
0
↑ i = 0
Check / comparison
G(0) = 0
Decision / next transition
Add 0.
Why this step matters

i = 0 (00_2): 0 ^ (0 >> 1) = 0 ^ 0 = 0 (00_2).

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<int> grayCode(int n) {
9 int total = 1 << n;
10 vector<int> res(total);
11 for (int i = 0; i < total; ++i) {
12 res[i] = i ^ (i >> 1);
13 }
14 return res;
15 }
16};
17
18int main() {
19 Solution sol;
20 auto res = sol.grayCode(2);
21 for (int v : res) cout << v << " ";
22 cout << endl; // 0 1 3 2
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Backtracking (DFS Hamiltonian Path)O(n * 2^n)O(2^n) visited set & recursion stackFrom 0, recursively try flipping bit 0 through n - 1 to find a Hamiltonian path across the n-dimensional hypercube.Search tree branching and backtracking.
2.Better — Mirror Reflection (Induction)O(2^n)O(1) auxiliaryStart with [0]. For bit i from 0 to n - 1, mirror existing elements in reverse order and add (1 << i).Reversed iteration.
3.Optimal — Direct Formula: i ^ (i >> 1)OptimalO(2^n)O(1) auxiliaryEvaluate G(i) = i ^ (i >> 1) for each i from 0 to 2n - 1 in a single linear loop.Output array allocation.

Common Pitfalls & Crucial Edge Cases

Using complex recursive backtracking when direct formula exists

i ^ (i >> 1) generates the sequence iteratively in O(1) per element.

Forgetting that 2^n elements are generated

Loop must run from 0 to (1 << n) - 1.

Shift overflow for n = 31

Use unsigned types if n reaches 31.

Crucial Edge Cases to Validate:

  • n = 1 — Sequence of 2 elements [0, 1].
  • n = 2 — Sequence of 4 elements [0, 1, 3, 2].
  • n = 16 — Generates 65536 elements; pre-allocating the vector size avoids reallocation overhead.
  • Cyclic property — The first element (0) and last element differ by exactly one bit.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Write out the closed-form formula G(i) = i ^ (i >> 1) and explain why shifting right aligns adjacent bits for XOR.
  2. Mention the inductive reflection property: an n-bit sequence is formed by the (n-1)-bit sequence followed by its reversed reflection with the leading bit set to 1.
  3. Cite real-world applications: rotary encoders, error correction in telecommunications, and genetic algorithms.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the defining property of an n-bit Gray code sequence?

2.What closed-form formula converts an integer i to its Gray code?

3.What is the time complexity to generate the full n-bit Gray code sequence?

Back to DSA Sheet