290. Reflected Code
A rotary dial has n switches. A scientist wants to visit every one of the 2^n switch settings (read each setting as an n-bit number) in a sequence where consecutive settings differ in exactly one switch, so each step flips a single bit. Such a sequence is called a reflected binary code.
Given n, return the standard one that starts at 0: the array of length 2^n whose element at index i equals i XOR (i >> 1), where >> is a right shift by one bit. The answer is checked for an exact match, so the order must be exactly this one, not just any valid cycle of settings.
For instance, with n = 2 the answer is [0, 1, 3, 2]. Searching for each next setting among the unused ones is too slow for large n; the direct formula takes O(2^n) time overall.
Example 1
- Input:
- n = 3
- Output:
- [0,1,3,2,6,7,5,4]
- Explanation:
The 8 entries are i ^ (i >> 1) for i = 0..7, e.g. it begins [0, 1, 3, 2].
Example 2
- Input:
- n = 5
- Output:
- [0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16]
- Explanation:
The 32 entries are i ^ (i >> 1) for i = 0..31, e.g. it begins [0, 1, 3, 2].
Example 3
- Input:
- n = 1
- Output:
- [0,1]
- Explanation:
The 2 entries are i ^ (i >> 1) for i = 0..1, e.g. it begins [0, 1].
Constraints
1 ≤ n ≤ 10
The output has exactly 2^n elements, with element i equal to i XOR (i >> 1).
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 240 msC++ 60 msJava 120 msJavaScript 120 msTypeScript 120 ms
Expected complexity
- Time
- O(2^n)
- Space
- O(2^n)