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: Generate a sequence of 2^n integers representing the n-bit Gray code. Adjacent numbers must differ by exactly one bit, and the sequence must start with 0. Multiple valid sequences can exist, but every consecutive pair must satisfy the one-bit difference rule.
Approach 1: Bit Manipulation Formula (O(2^n) time, O(1) extra space)
The most efficient way uses a direct mathematical relationship between binary numbers and Gray code. For any integer i, the Gray code value is i ^ (i >> 1). Iterate from 0 to 2^n - 1, apply this formula, and append the result to the output list. The right shift moves the binary representation one position, and XOR highlights the bit transitions, ensuring adjacent values differ by exactly one bit. This approach relies on properties of bit manipulation and avoids recursion or backtracking. Time complexity is O(2^n) because every Gray code number must be produced, while auxiliary space remains O(1) aside from the output array.
Approach 2: Recursive Gray Code Generation (O(2^n) time, O(2^n) space)
This method builds the sequence using the reflection property of Gray codes. Start with the base case for n = 1: [0, 1]. For each additional bit, take the existing sequence, reverse it, and prefix the reversed half with the new leading bit (value 1 << (n-1)). The first half keeps the original numbers, while the second half ensures only one bit changes between adjacent elements. This recursive construction mirrors how Gray codes are defined mathematically and is commonly explained using backtracking or recursive pattern building. The algorithm still generates 2^n values, giving O(2^n) time complexity and O(2^n) space for the stored sequence.
Recommended for interviews: The bit manipulation formula is usually what interviewers expect because it demonstrates strong understanding of binary operations and Gray code properties. The recursive reflection approach is also valid and easier to reason about conceptually, especially if the discussion involves math patterns behind Gray codes. Showing the recursive idea first and then optimizing with the i ^ (i >> 1) formula demonstrates both conceptual understanding and practical optimization.
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.
This C program calculates Gray codes by iterating from 0 to 2n - 1, computing each Gray code number using i ^ (i >> 1) for each integer i.
C++
Java
Python
C#
JavaScript
Time complexity: O(2n), traversing all numbers.
Space complexity: O(1), using constant extra space.
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 Gn-1 = [0, 1], then Gn = [0Gn-1, 1Gn-1].
This C implementation uses recursion to build the Gray code sequence by reflecting and appending. Allocate memory for the result array and fill it with generated codes.
C++
Java
Python
C#
JavaScript
Time complexity: O(2n), where recursions reflect and build upon previous results.
Space complexity: O(2n), allocating for the result array.
| Approach | Complexity |
|---|---|
| Using Bit Manipulation | Time complexity: O(2n), traversing all numbers. |
| Recursive Gray Code Generation | Time complexity: O(2n), where recursions reflect and build upon previous results. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation Formula (i ^ (i >> 1)) | O(2^n) | O(1) extra | Best for interviews and production code when you know the Gray code formula |
| Recursive Reflection Method | O(2^n) | O(2^n) | Useful for understanding Gray code construction or explaining the pattern step by step |
Gray Code Explained using Recursion and Backtracking | Leetcode#89 Solution in JAVA • Pepcoding • 42,187 views views
Watch 9 more video solutions →Practice Gray Code with our built-in code editor and test cases.
Practice on FleetCode