Gray Code

Medium
423.

Gray Code

Gray Code is a medium coding problem on math, bit manipulation and backtracking, asked in Amazon, Google and Microsoft interviews.

An n-bit gray code sequence is a permutation of 0 … 2^n - 1 that starts at 0, where consecutive entries differ in exactly one bit — and so do the first and the last entry.

Given n, return the standard reflected gray code sequence.

Example 1

Input
n = 2
Output
[0,1,3,2]

Example 2

Input
n = 1
Output
[0,1]

Example 3

Input
n = 0
Output
[0]

Constraints

  • 0 <= n <= 5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Gray Code — Solution in Python, Java & C++

Gray Code solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Gray Code is a medium coding problem on math, bit manipulation and backtracking, asked in Amazon, Google and Microsoft interviews.

Problem statement

An n-bit gray code sequence is a permutation of 0 … 2^n - 1 that starts at 0, where consecutive entries differ in exactly one bit — and so do the first and the last entry.

Given n, return the standard reflected gray code sequence.

Example 1

Input: n = 2
Output: [0,1,3,2]

Example 2

Input: n = 1
Output: [0,1]

Example 3

Input: n = 0
Output: [0]

Constraints

  • 0 <= n <= 5

Hints for Gray Code

  1. Hint 1

    There is a closed form: the i-th entry of the standard sequence is i XOR (i >> 1).

  2. Hint 2

    Check it: consecutive i differ in a run of low bits, and the XOR collapses that to a single bit flip.

  3. Hint 3

    The reflect-and-prefix construction produces exactly the same list.

How to solve Gray Code

The i-th entry of the standard reflected Gray code is i ^ (i >> 1).

Approach

  1. Return [i ^ (i >> 1) for i in 0 .. 2^n - 1].

Why it works

Consecutive integers differ in a run of low bits; XORing with the shifted value cancels all but one of those, leaving exactly one bit flip between consecutive entries, and the sequence is a bijection on 0..2^n - 1.

Complexity

  • Time — O(2^n)
  • Space — O(2^n)

Pitfalls

  • The reflect-and-prefix construction produces the same list recursively.

Reference solution

Python

def grayCode(n: int):
    return [i ^ (i >> 1) for i in range(1 << n)]

Java

public static int[] grayCode(int n) {
    int total = 1 << n;
    int[] out = new int[total];
    for (int i = 0; i < total; i++) out[i] = i ^ (i >> 1);
    return out;
}

C++

vector<int> grayCode(int n) {
    int total = 1 << n;
    vector<int> out(total);
    for (int i = 0; i < total; i++) out[i] = i ^ (i >> 1);
    return out;
}

JavaScript

var grayCode = function(n) {
    const total = Math.pow(2, n);
    const out = [];
    for (let i = 0; i < total; i++) out.push(i ^ (i >> 1));
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation · Backtracking