Gray Code (LeetCode 89): The Reflect-and-Prefix Trick and the One-Line Formula
Gray Code asks for a sequence of all 2^n n-bit numbers where neighbours differ in exactly one bit, starting at 0. It looks like a backtracking problem, and you can solve it that way, but interviewers usually want one of two cleaner ideas.
Idea 1: reflect and prefix
Start with the 1-bit sequence [0, 1]. To build the (k+1)-bit sequence, take the k-bit sequence, then append its mirror image with the new high bit set:
- n=1: 0, 1
- n=2: 00, 01, 11, 10
- n=3: 000, 001, 011, 010, 110, 111, 101, 100
Why it works: inside each half, neighbours already differ by one bit. At the seam, the last element of the first half and the first element of the mirrored half are the same number, except the second has the high bit set. And the very last element wraps back to 0 by one bit too.
def grayCode(n):
res = [0]
for k in range(n):
res += [x | (1 << k) for x in reversed(res)]
return res
Idea 2: the formula
The i-th Gray code is i ^ (i >> 1). Going from i to i+1 flips a run of trailing bits in i; XOR with the shifted value cancels all but one of those flips.
def grayCode(n):
return [i ^ (i >> 1) for i in range(1 << n)]
What to say in the interview
Lead with the reflection construction because it is easy to prove out loud, then mention the formula as the O(1)-per-element version. Both run in O(2^n) time, which is optimal since that is the output size. A common follow-up is decoding: to get i back from a Gray code g, XOR g with all of its right shifts.
If you want to rehearse explaining bit-manipulation problems like this under time pressure, I build an AI assistant for technical interviews at Linkjob AI (disclosure: it is my product). Practise the proof sketch, not just the code.
Further reading: Linkjob AI resource directory
评论
发表评论