Skip to main content

89. Gray Code

medium

Generate an n-bit Gray code sequence — every consecutive pair differs by exactly one bit. The closed-form trick: g(i) = i XOR (i >> 1).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

An n-bit gray code sequence is a sequence of 2^n integers where every integer is in the inclusive range [0, 2^n - 1], the first integer is 0, an integer appears no more than once in the sequence, the binary representation of every pair of adjacent integers differs by exactly one bit, and the binary representation of the first and last integers differs by exactly one bit. Given an integer n, return any valid n-bit gray code sequence.

Constraints

  • 1 <= n <= 16

Examples

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.

Example 2

Input
n = 1
Output
[0,1]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Recursive construction: take the (n-1)-bit gray code, prepend 0 to each, then take the reverse of the same list and prepend 1 to each.

Hint 2

Iterative closed form: g(i) = i XOR (i >> 1) for i from 0 to 2^n - 1.

Hint 3

Convince yourself the closed form is correct: consecutive i and i+1 differ at exactly the position of the lowest 0 bit of i (plus all trailing 1s flipping), and the XOR-shift transformation collapses that into a single-bit change.

Solution approach

Reveal approach

Closed-form construction. Build the result list of size 2^n. For i from 0 to (1 << n) - 1, push i ^ (i >> 1). That's the entire algorithm. Why it works: consecutive integers i and i+1 in binary differ at the lowest 0-bit of i and at every trailing 1-bit. After the XOR with the right-shifted version, all of those trailing changes cancel except for one, so g(i) and g(i+1) end up differing at exactly one bit. The last element g(2^n - 1) differs from g(0) = 0 at one bit too, closing the cycle. O(2^n) time and space for the output.

Complexity

Time
O(2^n)
Space
O(2^n) output

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Gray Code and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →