LeetCode #89 Medium

Gray Code

Generate an n-bit Gray code sequence where every consecutive pair, including the wraparound, differs by exactly one bit.

mathbit-manipulationbacktracking

Open on LeetCode ↗

02

Intuition

💡

The trap is trying to build the sequence by searching for a next value that differs from the current one by a single bit -- that's backtracking over an exponential space of 2^n candidates at each step, and it's completely unnecessary. There's a closed form: the i-th value in the sequence is simply i XOR (i >> 1). This formula guarantees the one-bit-difference property automatically, because XORing with a right-shifted copy of yourself only ever toggles one bit as i increments by one in binary -- you don't need to verify it, it falls out of the math. The invariant worth trusting: generate i from 0 to 2^n - 1 in plain counting order, apply the formula, and the single-bit-difference property (including the wrap from the last code back to 0) is guaranteed for free.

03

Approach

1

Compute the total count

The sequence has exactly 2^n entries for n bits, computed as 1 << n. This bounds the loop and requires no recursive exploration.

2

Apply the closed-form formula

For each i from 0 to 2^n - 1, compute i ^ (i >> 1) and append it to the result list. The right-shift-then-XOR pattern is what converts a normal binary counter into reflected binary (Gray) code.

3

Return the sequence directly

No backtracking, no adjacency checking, no undo -- the formula-generated list already satisfies the required property between every consecutive pair and between the last and first elements.

04

Solution & live demo

python

▶1class Solution:
▶2    def grayCode(self, n: int) -> list[int]:
▶3        total = 1 << n
▶4        result = []
▶5        for i in range(total):
▶6            result.append(i ^ (i >> 1))
▶7        return result

05

Edge cases

n = 0

1 << 0 = 1, loop runs once for i=0, returns [0]

n = 1

returns [0, 1], the smallest real Gray code toggle

wraparound from last to first

guaranteed by the formula's structure, no explicit check needed

larger n (e.g. n=5)

formula scales identically, still O(2^n) time with no extra bookkeeping

06

Complexity

Time

O(2^n)

Space

O(2^n)

must produce all 2^n codes; each is O(1) to compute