Circular Permutation in Binary Representation — LeetCode 1238 Python Solution

The problem

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1) such that : p[0] = start p[i] and p[i+1] differ by only one bit in their binary representation.

Example

Input

n = 2, start = 3

Output

[3,2,0,1]

Explanation

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

Python solution

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        g = [i ^ (i >> 1) for i in range(1 << n)]
        j = g.index(start)
        return g[j:] + g[:j]

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1238. Circular Permutation in Binary Representation is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems