Gray Code - Video Solutions

Problem 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.