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 <= 16The Gray Code problem asks you to generate a sequence of integers representing an n-bit Gray code, where consecutive values differ by exactly one bit. A key observation is that Gray codes follow a predictable pattern that can be constructed without checking every pair.
One common strategy is the reflection method. Start with the base case for 0 bits and iteratively build larger sequences by reflecting the existing list and prefixing bits appropriately. This ensures that adjacent numbers differ by only one bit. Another elegant perspective uses bit manipulation, where each index can be transformed into its Gray code equivalent using a simple bitwise relationship involving right shifts and XOR operations.
Both approaches generate all 2^n values in the sequence. Since every Gray code must be produced, the time complexity grows exponentially with n, while the space complexity is dominated by storing the resulting list.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Reflection / Iterative Construction | O(2^n) | O(2^n) |
| Bit Manipulation Formula | O(2^n) | O(2^n) |
Pepcoding
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.
Time complexity: O(2n), traversing all numbers.
Space complexity: O(1), using constant extra space.
1#include <stdio.h>
2#include <math.h>
3
4void grayCode(int n) {
5 int size = pow(2, n);
6 for (int i = 0; i < size; i++) {
7 int gray = i ^ (i >> 1);
8 printf("%d ", gray);
9 }
10}
11
12int main() {
13 int n = 2;
14 grayCode(n);
15 return 0;
16}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.
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].
Time complexity: O(2n), where recursions reflect and build upon previous results.
Space complexity: O(2n), allocating for the result array.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Gray Code and similar bit manipulation problems occasionally appear in FAANG-style interviews. They test understanding of binary representations, bitwise operations, and the ability to recognize patterns in sequence generation.
The optimal approach uses bit manipulation or the reflection technique to generate the sequence efficiently. Both methods produce each of the 2^n values directly while maintaining the one-bit difference rule between consecutive numbers.
Gray Code is designed so that consecutive numbers differ by exactly one bit to minimize transition errors in digital systems. This property also makes it useful in algorithmic problems where controlled state transitions are required.
A dynamic list or array is typically used to store the resulting sequence of Gray codes. During construction, operations like appending and iterating through existing values make arrays or vectors the most practical choice.
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.