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.
- Difficulty: Medium
- Topics: Math, Bit Manipulation, Backtracking
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
There is a closed form: the i-th entry of the standard sequence is
i XOR (i >> 1).Hint 2
Check it: consecutive
idiffer in a run of low bits, and the XOR collapses that to a single bit flip.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
- 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