#1238

Circular Permutation in Binary Representation

pupil · 560 · lc medium +28 · verified · 72.6% accepted · 441 likes · top 82%

Description

Given integers n and start, find any permutation p of all integers from 0 to 2ⁿ - 1 satisfying:

- p[0] = start

- Any two consecutive elements p[i] and p[i+1] differ by exactly one bit in their binary representations.

- The first and last elements p[0] and p[2ⁿ - 1] also differ by exactly one bit.

Example 1:

Input: n = 2, start = 3

Output: [3,2,0,1]

Explanation: The binary representation of the permutation is (11,10,00,01).

All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2

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

Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Code

1

2

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]: