Watch 10 video solutions for Gray Code, a medium level problem involving Math, Backtracking, Bit Manipulation. This walkthrough by Pepcoding has 44,256 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
An n-bit gray code sequence is a sequence of 2n integers where:
[0, 2n - 1],0,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 <= 16Problem 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 | 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. |