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.
p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

 
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).

 
Constraints:

1 <= n <= 16
0 <= start < 2 ^ n

Difficulty: interview

Starter code:

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

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

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


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        res,s = [],None
        for i in range(1<<n):
            tmp = i^(i>>1)
            res.append(i^(i>>1))
            if tmp == start:
                s = i
        res += res
        return res[s:s+len(res)//2]


from collections import defaultdict, deque


def gen_perm(n):
    if n == 1:
        return [0, 1]
    else:
        gen_prev = gen_perm(n - 1)
        right = [2 ** (n - 1) + num for num in gen_prev]
        return gen_prev + list(reversed(right))
    
        
class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        perm = gen_perm(n)
        i = 0
        while perm[i] != start:
            i += 1
        return perm[i:] + perm[:i]

class Solution:
    def helper(self, n):
        return n ^ (n >> 1)
    def circularPermutation(self, n: int, start: int) -> List[int]:
        solution = list()
        for i in range(0, 2 ** n):
            solution.append(self.helper(i))
        index = -1
        for i in range(0, len(solution)):
            if solution[i] == start:
                index = i
                break
        # print(solution)
        return solution[index:] + solution[:index]


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        gray=[]
        for i in range(2**n):
            gray.append(i^(i>>1))
            if start==i^(i>>1):
                index=i
        return gray[index:]+gray[0:index]


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        gray = []
        for i in range(2**n):
            gray.append(i ^ (i >> 1))
        idxStart = gray.index(start)
        # print(gray)
        result = []
        for i in range(len(gray)):
            result.append(gray[(i+idxStart)%len(gray)])
        return result
                    


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

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        gc, bit = [0, 1], 1
        while bit < n:
            bit += 1

            next_vals = []
            for val in reversed(gc):
                next_vals.append( val + 2**(bit-1) )
            gc.extend(next_vals)

        ind = gc.index(start)
        return gc[ind:] + gc[:ind]

class Solution:
    def helper(self, n):
      if n == 1:
        return ['0', '1']
      else:
        res = self.helper(n-1)
        return ['0' + x for x in res] + ['1' + x for x in res[::-1]]
      
    def circularPermutation(self, n: int, start: int) -> List[int]:
      res = [(int)(n,2) for n in self.helper(n)]
      return res[res.index(start):] + res[:res.index(start)]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        a = ['0', '1']
        
        for i in range(n-1):
            a0 = ['0'+b for b in a]
            a1 = ['1'+b for b in a]
            a = a0 + a1[::-1]
            
        intperm = [int(b, 2) for b in a]
        idx = intperm.index(start)
        
        return intperm[idx:]+intperm[:idx]


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        bi = str(bin(start))[2:].zfill(n)
        def get_perm(bi_start, l):
            a = bi_start[-1*l]
            b = str(1 - int(a))
            if l == 1: return [a, b]
            perms = get_perm(bi_start, l-1)
            return [a+e for e in perms] + [b+e for e in perms[::-1]]
        return list(map(lambda x: int(x, 2), get_perm(bi, len(bi))))

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        res=[0]*(1<<n)
        for i in range(1<<n):
            res[i]=start^i^i>>1
        return res

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        def generateGray(n):
            if (n <= 0):
                return

            arr = list()

            arr.append(\"0\")
            arr.append(\"1\")

            i = 2
            j = 0
            while(True):

                if i >= 1 << n:
                    break

                for j in range(i - 1, -1, -1):
                    arr.append(arr[j])

                for j in range(i):
                    arr[j] = \"0\" + arr[j]

                for j in range(i, 2 * i):
                    arr[j] = \"1\" + arr[j]
                i = i << 1

            return arr
        
        def rotateArr(arr, i):
            return arr[-i:] + arr[:-i]
        
        arr = generateGray(n)
        start = \"{0:b}\".format(start)
        res = ''
        if len(start) != n:
            d = n - len(start)
            for i in range(d):
                res += '0'
            start = res + start
        arr = rotateArr(arr, len(arr) - arr.index(start))
        return list(map(lambda x: int(x, 2), arr))

class Solution:
    def helper(self, n):
      if n == 1:
        return ['0', '1']
      else:
        res = self.helper(n-1)
        return ['0' + x for x in res] + ['1' + x for x in res[::-1]]
      
    def circularPermutation(self, n: int, start: int) -> List[int]:
      #res = [(int)(n,2) for n in self.helper(n)]
      #return res[res.index(start):] + res[:res.index(start)]
      gray_code = ['0', '1']
      n -= 1
      while n > 0:
        gray_code = ['0' + x for x in gray_code] + ['1' + x for x in gray_code[::-1]]
        n -= 1
      gray_code = [(int)(x,2) for x in gray_code]
      return gray_code[gray_code.index(start):] + gray_code[:gray_code.index(start)]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        def extendPerm(arr):
            arr.extend(['1'+num for num in arr[::-1]])
            for i in range(len(arr) // 2):
                arr[i] = '0' + arr[i]
        arr = ['0', '1']
        for i in range(n-1):
            extendPerm(arr)
        nums = [int(num, 2) for num in arr]
        index = nums.index(start)
        return nums[index:] + nums[:index]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        currentList = [\"0\", \"1\"]
        
        from copy import deepcopy
        
        for idx in range(n-1):
            length_prev = len(currentList)
            for idx in range(length_prev-1, -1, -1):
                currentList.append(\"1\"+currentList[idx])
            
            for idx in range(length_prev):
                currentList[idx] = \"0\"+currentList[idx]
                
        for idx in range(len(currentList)):
            currentList[idx] = int(currentList[idx], 2)
         
        idx = currentList.index(start)
        currentList = currentList[idx:] + currentList[:idx]
        return currentList
            
            

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        # generate the Gray code for `n` bits
        gray_code = [1, 0]
        for i in range(1, n):
            next_gray_code = []
            increase = 1 << i
            for num in gray_code:
                next_gray_code.append(num + increase)
            for num in reversed(gray_code):
                next_gray_code.append(num)
            gray_code = next_gray_code
        # then rotate the list backwards until `start` is at the beginning
        idx = gray_code.index(start)
        return gray_code[idx:] + gray_code[:idx]

class Solution:
    def circularPermutation(self, n, start):
        start = bin(start)[2:]
        
        while len(start) != n:
            start = '0' + start
         
        nums = [start]
        for i in range(n):
            tmp = []
            for j in nums[::-1]:
                if j[i] == '1':
                    tmp.append(j[:i] + '0' + j[i+1:])
                else:
                    tmp.append(j[:i] + '1' + j[i+1:])
            nums += tmp
        return [int(i, 2) for i in nums]

class Solution:
    def circularPermutation(self, n, start):
        def g(x):
            return x^(x>>1)    
        
        return [start ^ g(i) for i in range(1 << n)]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        res = []
        
        for i in range(2**n):
            res.append((i>>1)^i)
        
        idx = res.index(start)
        return res[idx:]+res[:idx]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        used = {start}
        two = [2**i for i in range(n)]
        res = [start]

        while len(res) < 2**n :
            i = 0
            a = res[-1]^two[i]
            while a in used:
                i+= 1
                a = res[-1]^two[i]

            used.add(a)
            res.append(a)
        return res

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


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

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        return self.generateGrayArrWithCondition(n, start)
    
    def generateGrayArrWithCondition(self, n, start):
        arr = []

        arr.append(\"0\") 
        arr.append(\"1\") 

        i = 2
        j = 0
        while(True): 
            if i >= 1 << n: 
                break

            for j in range(i - 1, -1, -1): 
                arr.append(arr[j]) 

            for j in range(i): 
                arr[j] = \"0\" + arr[j] 

            for j in range(i, 2 * i): 
                arr[j] = \"1\" + arr[j] 
            i = i << 1

        for index, element in enumerate(arr):
            arr[index] = int(element, 2)
            if arr[index] == start:
                break_at = index
            
        return arr[break_at:] + arr[:break_at]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        return self.solve(start, n)
    def solve(self, num, length):
        if length==1:
            if num==1:
                return [1, 0]
            return [0, 1]
        firstnum=1
        if num<2**(length-1):
            firstnum=0
        res=self.solve(num-firstnum*2**(length-1), length-1)
        ans=[]
        for i in res:
            ans.append(firstnum*2**(length-1)+i)
        res.reverse()
        for i in res:
            ans.append((1-firstnum)*2**(length-1)+i)
        return ans

class Solution:\r
    def circularPermutation(self, n: int, start: int) -> List[int]:\r
        result = list(range(1 << n))\r
\r
        def reverse(lst, i, j):\r
            while i < j:\r
                lst[i], lst[j] = lst[j], lst[i]\r
                i, j = i + 1, j - 1\r
\r
        for i in range(1, n):\r
            for j in range(1, (1 << (n - i)) + 1, 2):\r
                reverse(result, j << i, ((j + 1) << i) - 1)\r
\r
        start_idx = result.index(start)\r
        result = result[start_idx: 1 << n] + result[0: start_idx]\r
        return result

from itertools import chain

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        start_mask = start;
        while start_mask:
            start_mask >>= 1;
            start ^= start_mask;
        out = [x ^ (x >> 1) for x in chain(range(start, 2 ** n), range(start))]
        # print(out)
        return out

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        # dp = [0, 1]
        # for i in range(1, n):
        #     dp2 = dp + [d | 1 << i for d in dp[::-1]]
        #     dp = dp2
        
        # Alternatively, using Gray Code
        dp = [i ^ i >> 1 for i in range(1 << n)]
        idx = dp.index(start)
        return dp[idx:] + dp[: idx]





class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        prv_code = self.grayCode(n-1)
        return prv_code + [2 ** (n-1) + x for x in reversed(prv_code)]
    
    def circularPermutation(self, n: int, start: int) -> List[int]:
        ind=self.grayCode(n).index(start)
        
        
        return self.grayCode(n)[ind:]+self.grayCode(n)[:ind]
        
        


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        # dp = [0, 1]
        # for i in range(1, n):
        #     dp2 = dp + [d | 1 << i for d in dp[::-1]]
        #     dp = dp2
        # idx = dp.index(start)
        # return dp[idx:] + dp[: idx]
        
        # Alternatively, using Gray Code
        return [start ^ i ^ i >> 1 for i in range(1 << n)]
        


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        answer = [start]
        visited = set(answer)
        
        next = start
        while (next != None): 
            previous = next
            next = None
            for i in range(n):
                newNum = previous ^ (1 << i)
                # print(i, newNum, previous)
                if newNum not in visited:
                    visited.add(newNum)
                    answer.append(newNum)
                    next = newNum
                    break
            
        return answer

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        perms = [2 ** i for i in range(n-1, -1, -1)]
        
        end = start ^ 1
        
        visited = set()
        path = []
        
        def dfs(node):
            if node == end:
                path.append(node)
                return True
            
            if node in visited: return False
            
            visited.add(node)
            
            for perm in perms:
                if dfs(node ^ perm):
                    path.append(node)
                    return True
            return False
        
        dfs(start)
        return reversed(path)

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        return [start^i^(i>>1) for i in range(2**n)]


class Solution:\r
    def circularPermutation(self, n: int, start: int) -> List[int]:\r
        result = list(range(1 << n))\r
\r
        def reverse(lst, i, j):\r
            print(i, j)\r
            while i < j:\r
                lst[i], lst[j] = lst[j], lst[i]\r
                i, j = i + 1, j - 1\r
\r
        for i in range(1, n):\r
            for j in range(1, (1 << (n - i)) + 1, 2):\r
                reverse(result, j << i, ((j + 1) << i) - 1)\r
\r
        start_idx = result.index(start)\r
        result = result[start_idx: 1 << n] + result[0: start_idx]\r
        return result

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        used = set()
        result = [None] * int(2**n)
        result[0] = start
        used.add(start)
        for i in range(1, len(result)):
            for x in range(n):
                bit = bool(result[i-1] & (1<<x))
                if bit:
                    val = result[i-1] - (1<<x)
                else:
                    val = result[i-1] + (1<<x)
                if val not in used:
                    used.add(val)
                    result[i] = val
                    break
        return result

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        
        array = list(map(self.binaryToGray, range(0, 2 ** n)))
        index = array.index(start)

        return array[index: ] + array[: index]

    def binaryToGray(self, n: int) -> int:
        return n ^ (n >> 1)

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        ans = []
        lastNumberSet = set([start^(1<<i) for i in range(n)])
        nMax = 2**n
        
        visited = set()
        visited.add(start)
        def helper(preNum, ni):
            if ni == nMax:
                if preNum in lastNumberSet:
                    return True
                return False
            for i in range(n):
                nextNum = preNum^(1<<i)
                if nextNum not in visited:
                    visited.add(nextNum)
                    if helper(nextNum, ni+1):
                        ans.append(nextNum)
                        return True
                    visited.remove(nextNum)
            return False
        
        helper(start, 1)
        return [start] + ans[::-1]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        original_list = [None for _ in range(1 << n)]
        original_list[0] = 0
        original_list[1] = 1
        for i in range(1, n):
            num_elements = 1 << i
            for j in range(num_elements):
                original_list[j] <<= 1
            for j in range(num_elements):
                original_list[num_elements + j] = original_list[num_elements - j - 1] + 1
        
        result_list = [None for _ in range(1 << n)]
        current = 0
        while original_list[current] != start:
            current += 1
            
        for i in range(1 << n):
            result_list[i] = original_list[(current + i) % (1 << n)]
        
        return result_list


class Solution:
    def backtracking(self,result,visited,n,found):
        if len(result) == 2 ** n:
            diff = result[-1] ^ result[0]
            i = 0
            is_one_bit = 0
            while i<n:
                if (1 << i) == diff:
                    is_one_bit = 1
                    break
                i = i + 1
            if is_one_bit == 1:
                found[0] = 1
            return
        if found[0] == 1:
            return
        start = result[-1]
        for i in range(n):
            num = start ^ (1 << i)
            if num in visited or num<0 or num>=2 ** n:
                continue
            result.append(num)
            visited[num] = 1
            self.backtracking(result,visited,n,found)
            if found[0] == 1:
                return
            visited.pop(num)
            result.pop()
        
    def circularPermutation(self, n: int, start: int) -> List[int]:
        if n == 0:
            return [0]
        result = [start]
        found = [0]
        visited = {}
        visited[start] = 1
        self.backtracking(result,visited,n,found)
        return result

class Solution:
    def backtracking(self,result,visited,n,found):
        if len(result) == 2 ** n:
            diff = abs(result[-1] - result[0])
            while diff%2 == 0:
                diff = diff/2
            if diff == 1:
                found[0] = 1
            return
        if found[0] == 1:
            return
        start = result[-1]
        for i in range(n):
            num = start ^ (1 << i)
            if num in visited or num<0 or num>=2 ** n:
                continue
            result.append(num)
            visited[num] = 1
            self.backtracking(result,visited,n,found)
            if found[0] == 1:
                return
            visited.pop(num)
            result.pop()
        
    def circularPermutation(self, n: int, start: int) -> List[int]:
        if n == 0:
            return [0]
        result = [start]
        found = [0]
        visited = {}
        visited[start] = 1
        self.backtracking(result,visited,n,found)
        return result

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        def dfs(i):
            if len(p) == 1 << n:
                a = p[0] ^ p[1]
                return a and a & (a - 1) == 0
            j = 1
            for _ in range(n):
                k = i ^ j
                if k not in visited:
                    visited.add(k)
                    p.append(k)
                    if dfs(k):
                        return True
                    visited.remove(k)
                    p.pop()
                j <<= 1
            return False
        
        visited = {start}
        p = [start]
        dfs(start)
        return p

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        ans = []
        lastNumberSet = set([start^(1<<i) for i in range(n)])
        nMax = 2**n
        
        visited = set()
        visited.add(start)
        
        def helper(preNum, ni):
            if ni == nMax:
                if preNum in lastNumberSet:
                    return True
                return False
            for i in range(n):
                nextNum = preNum^(1<<i)
                if nextNum not in visited:
                    visited.add(nextNum)
                    if helper(nextNum, ni+1):
                        ans.append(nextNum)
                        return True
                    visited.remove(nextNum)
            return False
        
        helper(start, 1)
        return [start] + ans[::-1]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        def encode_as_gray(n):
            return n ^ (n >> 1)
        arr = [encode_as_gray(i) for i in range(0, 2 ** n)]
        i = arr.index(start)
        return arr[i:] + arr[:i]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        gc = [0]
        for i in range(1,2**n):
            gc.append(gc[-1] ^ (i & -i)) # -i is similar to two component https://leetcode.com/problems/gray-code/discuss/245076/4-lines-Elegant-fast-and-easy-understand-Python-solution/688127 and https://stackoverflow.com/a/12250963/8006144
            
        l = len(gc)
        for i in range(l):
            fe = gc[0]
            if fe == start:
                break
            else:
                gc.append(gc.pop(0))
        return gc


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        k=1
        ans=[0,1]
        while k<=n-1:
            l=len(ans)
            for i in range(l-1,-1,-1):
                ans.append((2**k)+ans[i])
            k=k+1
        while 1:
            if ans[0]==start:
                break
            else:
                ans.append(ans.pop(0))
        return ans

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        def f(n):
            if n == 0: return [0]
            else:
                return f(n-1) + [2**(n-1) + v for v in f(n-1)[::-1]]
        res = f(n)
        i = res.index(start)
        return res[i:] + res[:i]
        


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

class Solution:
\tdef circularPermutation(self, n: int, start: int) -> List[int]:
\t\tres=[]
\t\tfor i in range(2**n):
\t\t\tres.append(i^(i>>1))
\t\tstack=[]
\t\ttem=[]
\t\tfor j in range(len(res)):
\t\t\tif res[j]!=start:
\t\t\t\tstack.append(res[j])
\t\t\telse:
\t\t\t\ttem=res[j:]
\t\t\t\tbreak
\t\tans=tem+stack
\t\treturn ans


class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        def encode_as_gray(n):
            return n ^ (n >> 1)
        arr = [encode_as_gray(i) for i in range(0, 2 ** n)]
        i = arr.index(start)
        return arr[i:] + arr[:i]

        return array[index: ] + array[: index]

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        r = [0, 1]
        for i in range(1, n):
            r += [2 ** i + v for v in r[::-1]]
        idx = r.index(start)
        return r[idx:] + r[:idx]