Reflected Binary Sequence

MEDIUM25 pts

A reflected binary sequence of order n is a specific arrangement of 2ⁿ distinct integers with unique mathematical properties. This sequence has the following characteristics:

Every integer in the sequence is within the inclusive range [0, 2ⁿ - 1].
The sequence must begin with 0.
Each integer must appear exactly once in the sequence (no duplicates).
For every pair of consecutive elements in the sequence, their binary representations must differ by exactly one bit (Hamming distance of 1).
The binary representations of the first and last elements in the sequence must also differ by exactly one bit, forming a cyclic chain.

This sequence is particularly useful in digital communications and error minimization applications because consecutive values change minimally, reducing the chance of errors during transitions.

Given a positive integer n representing the order of the sequence, generate and return any valid reflected binary sequence of that order. Multiple correct sequences may exist for a given n, and any one of them is acceptable as output.

Example

Input

n = 2

Output

[0,1,3,2]

Explanation

The binary representations of [0,1,3,2] are [00,01,11,10].

00 and 01 differ by exactly one bit (rightmost bit)
01 and 11 differ by exactly one bit (leftmost bit)
11 and 10 differ by exactly one bit (rightmost bit)
10 and 00 differ by exactly one bit (leftmost bit), completing the cycle

Alternative valid sequences include [0,2,3,1] with binary [00,10,11,01], which also satisfies all constraints.

Example

Input

n = 1

Output

[0,1]

Explanation

With n=1, we have 2¹ = 2 elements in the range [0,1]. The sequence [0,1] represents binary [0,1], where 0 and 1 differ by exactly one bit.

Example

Input

n = 3

Output

[0,1,3,2,6,7,5,4]

Explanation

The binary representations are [000,001,011,010,110,111,101,100]. Each consecutive pair differs by exactly one bit, and the first (000) and last (100) elements also differ by one bit.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 16
The output sequence must contain exactly 2ⁿ elements.
Every adjacent pair must differ by exactly one bit in binary representation.
Any valid sequence satisfying all conditions is acceptable.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

n =

Reflected Binary Sequence

Hints

Reflected Binary Sequence

Hints