Coding Interview PatternsGray Code
MediumBitwise Manipulation

Gray Code

Explanation & Solution

Practice Problem

Description

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
  • The binary representation of the first and last integers also differ by exactly one bit

Given an integer n, return any valid n-bit gray code sequence.

Input: n = 2

Output:[0,1,3,2]
0
0
1
1
2
3
3
2

Explanation:

  • 00 - 0
  • 01 - 1
  • 11 - 3
  • 10 - 2

Constraints

  • 1 <= n <= 16

Approach

Bitwise Manipulation pattern

Key Insight

  • The standard reflected Gray code has a clean bitwise formula: Gray(i) = i XOR (i >> 1)
  • Time: O(2^n) | Space: O(2^n)

Solution Code

Previous
Total Hamming Distance
Next
Decode XORed Array