89. Gray Code
mediumGenerate an n-bit Gray code sequence — every adjacent pair differs by exactly one bit, and the first and last entries also differ by one bit. Beautiful recursive construction using mirror-and-prepend.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
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, 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.
Constraints
1 <= n <= 16
Examples
Example 1
n = 2[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
Example 2
n = 1[0,1]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Recursive 'reflect and prepend' construction. Gray(n) = Gray(n-1) followed by reverse(Gray(n-1)) with 1 prepended in the higher bit.
Hint 2
Gray(1) = [0, 1]. Gray(2) = [00, 01] + [11, 10] = [0, 1, 3, 2].
Hint 3
Iterative O(2^n): for i from 0 to 2^n - 1, output i XOR (i >> 1). Very fast, very compact.
Hint 4
Either solution is accepted.
Solution approach
Reveal approach
Two clean approaches. Recursive 'reflect and prepend': Gray(n) base case is Gray(0) = [0] or Gray(1) = [0, 1]. For n > 1, get prev = Gray(n - 1); compute result by appending prev plus prev iterated in reverse with the (n-1)-th bit set. result = prev + [(1 << (n - 1)) | x for x in reverse(prev)]. The reflection ensures the boundary between the two halves only differs in the new high bit. Iterative formula: for i in [0, 2^n) output i ^ (i >> 1). Both run in O(2^n) time and O(2^n) output. The XOR trick is the production-grade implementation; the reflect-and-prepend version is what you should explain in interviews because it shows the recursive structure.
Complexity
- Time
- O(2^n)
- Space
- O(2^n)
Related patterns
- recursion
- bit-manipulation
- reflection
Related problems
- 1238. Gray Code
- 477. Total Hamming Distance
- 78. Subsets
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
Practice these live with InterviewChamp.AI
Drill Gray Code and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →