Problem Statement in English

The problem is to generate a sequence of integers from $0$ to $2^n - 1$ such that each consecutive pair of integers differs by exactly one bit in their binary representation. This sequence is known as the Gray code.

Approach

Taking a binary number and XORing it with itself shifted right by one bit produces the corresponding Gray code. Furthermore, it is guaranteed that each binary number has a single unique Gray code representation, and it will not produce duplicates.

The reason it works is that the Gray code bit that changes is always the leftmost bit that flipped during the original binary increment (the previous number + 1). Every other flipped bit has a flipped neighbor to its left, so XOR cancels out the effect of both flips. The leftmost flipped bit is the only one whose left neighbor didn’t flip.

This is because when you increment a binary number, the rightmost bits that are 1 will flip to 0, and the first 0 bit to the left of those will flip to 1. No bits after the first 0 bit will change. The XOR operation captures this change, resulting in a Gray code where only one bit changes between consecutive numbers.

And we’re done!

Solution in Python


class Solution:
    def grayCode(self, n: int) -> List[int]:
        result = [0]

        for i in range(n):
            for num in reversed(result):
                result.append(num | (1 << i))

        return result

Complexity

  • Time: $O(2^n)$
    Since we are generating all $2^n$ Gray codes, the time complexity is $O(2^n)$.

  • Space: $O(1)$
    Since we are modifying the result list in place and not using any additional data structures that scale with input size, the space complexity is $O(1)$.

Mistakes I Made

I had to look this up :(

And we are done.