Gray Code

Gray Code

What is this problem about?

The Gray Code interview question asks you to generate a sequence of $2^n$ integers representing an $n$-bit Gray code sequence. A Gray code sequence is an ordering of binary numbers such that two successive values differ in only one bit. The sequence must begin with 0. For example, for $n=2$, the sequence [0, 1, 3, 2] in binary is [00, 01, 11, 10]. Notice how each step changes exactly one bit.

Why is this asked in interviews?

Companies like Microsoft and Amazon use this Bit Manipulation and Math interview pattern to test a candidate's knowledge of boolean logic and recursive generation algorithms. It evaluates whether you can recognize the mirror/reflection pattern inherent in Gray codes or if you know the direct bitwise formula to convert a standard binary number to its Gray code equivalent.

Algorithmic pattern used

There are two primary ways to solve this:

1. Reflection / Backtracking (Intuitive):
   • Start with base sequence for $n=1$: [0, 1].
   • To get $n=2$, take the previous sequence [0, 1], reflect it to get [1, 0], and add a leading '1' to the reflected part ([1+2, 0+2] -> [3, 2]). Combine them: [0, 1, 3, 2].
   • Repeat this reflection and prefixing process until you reach the desired $n$.
2. Bitwise Formula (Optimal O(1) per element):
   • The $i^{th}$ number in the Gray code sequence can be generated directly using the formula: i ^ (i >> 1).

Example explanation

Using the Reflection method for $n = 3$:

1. $n=1$: [0, 1]
2. $n=2$:
   • Original: [0, 1]
   • Reversed: [1, 0]
   • Add $2^1$ (which is 2) to reversed: [3, 2]
   • Combined: [0, 1, 3, 2]
3. $n=3$:
   • Original: [0, 1, 3, 2]
   • Reversed: [2, 3, 1, 0]
   • Add $2^2$ (which is 4) to reversed: [6, 7, 5, 4]
   • Combined: [0, 1, 3, 2, 6, 7, 5, 4]

Common mistakes candidates make

• Brute Force Search: Trying to use generic backtracking to "guess" the next number that differs by one bit. While this works, it's slow and overly complex compared to the structured reflection method.
• Bit Math Errors: Using the wrong bitwise operators when trying to implement the direct formula (e.g., using AND instead of XOR).

Interview preparation tip

The formula G(i) = i ^ (i >> 1) is a classic computer science trivia fact. If you memorize it, you can solve this problem in a 3-line loop. However, always be prepared to explain the "reflection" logic if the interviewer asks why the formula works.