List every n-bit number so each differs from the next by exactly one bit. Start with 0, then for each new bit mirror the list and switch that bit on in the mirrored half; the seam changes only the new bit. Same as i XOR (i >> 1).
▼The problem
LeetCode 89 (Medium). Given n, return any valid n-bit Gray code sequence: 2ⁿ distinct numbers in [0, 2ⁿ), starting at 0, where every pair of neighbours, and the last and first numbers, differ in exactly one bit.
Examples (LeetCode's): n = 2 → [0,1,3,2] (00, 01, 11, 10; the example scene); n = 1 → [0,1] (checked, not shown).
The solution
def grayCode(n):
res = [0]
for i in range(n):
bit = 1 << i
res += [x + bit for x in reversed(res)]
return res
def grayCode(n): # closed form
return [i ^ (i >> 1) for i in range(1 << n)]Transcript
Gray Code. Given n, list all two to the n numbers with n bits, starting at zero, so each one differs from the next in exactly one bit, including the wrap from the last back to the first.
Take n equals two. Zero zero, zero one, one one, one zero. That's zero, one, three, two. Every step flips one bit, even from two back to zero.
The slow way is a search. From zero, flip a bit to reach a number you haven't used, and back up when you get stuck. It works, but it can take exponential time.
Instead, reflect and prefix. Start with just zero. To add a bit, append the list in reverse, like a mirror image, with the new top bit switched on. At the seam, the two numbers match except for that bit, and the same goes for the two ends.
Let's build three bits. Zero. Mirror it and add one: zero, one. Mirror and add two: three, two. Mirror and add four: six, seven, five, four. Eight numbers, each one bit away from the next.
In code, start with a list holding zero. For each bit, extend it with the reversed list plus that bit. Or use the closed form: number i is i XOR i shifted right by one. Five XOR two is seven, a match.
We make two to the n numbers with constant work each, so the time matches the output size. Extra space is constant.
Start at zero, mirror the list, switch on the new bit. That's Gray Code.