Reflected Gray Dial
MediumBit Manipulation
Problem
A rotary encoder with n tracks labels its 2^n positions so that turning the dial one step changes exactly one track. It uses the reflected sequence, defined recursively: for n = 0 the sequence is [0]; for n ≥ 1, take the sequence for n - 1, then append the same sequence in reverse order with bit n - 1 set on every element.
Return the reflected sequence for n tracks as an array of 2^n integers.
Example 1
- Input:
- n = 2
- Output:
- [0, 1, 3, 2]
[0, 1] followed by reversed [1, 0] with bit 1 added: [3, 2].
Example 2
- Input:
- n = 3
- Output:
- [0, 1, 3, 2, 6, 7, 5, 4]
Example 3
- Input:
- n = 0
- Output:
- [0]
Constraints
- 0 ≤ n ≤ 16
Hint
Show the first hint
Write out the sequence for n = 3 next to the numbers 0..7 in binary. Do you see a per-index formula?
Walkthrough
How to approach it
01Clarify before coding
- Is any one-bit-change sequence accepted? No: it must be the reflected one defined in the statement, so the answer is unique.
- Does the sequence start at 0? Yes, by the definition for n = 0.
- How big can the output get? 2^16 = 65536 values.
02Brute force
Implement the definition literally: start from [0] and for each new bit append the reversed copy with that bit OR-ed in.
Cost: O(2^n) time and space, which is already optimal; the interviewer is fishing for the closed form that computes any position directly.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.