# Circular Permutation in Binary Representation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/circular-permutation-in-binary-representation)
Canonical: https://scaleengineer.com/dsa/problems/circular-permutation-in-binary-representation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## 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.
* `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`

# Approaches
## Backtracking Search
This approach uses a classic backtracking algorithm to explore all possible permutations. It builds the sequence one number at a time, ensuring each new number satisfies the single-bit-difference rule. If it reaches a dead end, it backtracks to try another path. This is conceptually a search for a Hamiltonian Path in an n-dimensional hypercube graph.
**Time:** O(n * 2^n). The recursion can have a depth of `2^n`. At each step, we explore up to `n` possible next elements by flipping each bit of the current number. · **Space:** O(2^n). This space is used for the recursion stack (which can go up to `2^n` deep), the `visited` set, and the `result` list.
**Pros:** It's a general approach for path-finding problems and is guaranteed to find a solution if one exists.; Conceptually straightforward for those familiar with recursion and backtracking.
**Cons:** Significantly slower than other approaches due to its exponential nature.; May result in a 'Time Limit Exceeded' error for larger values of `n` (e.g., `n=16`).
### Explanation
The algorithm starts with a list containing only the `start` element. A `visited` set is used to keep track of numbers that are already part of the sequence to avoid cycles and redundant computations. A recursive function is defined to build the permutation. In each recursive call, it takes the last element added to the sequence and tries to find a valid next element by flipping each of its `n` bits one by one. A candidate is valid if it hasn't been visited yet. If a valid candidate is found, it's added to the sequence, and the function calls itself. If the recursive call fails to find a complete path, the candidate is removed (this is the backtracking step). The base case for the recursion is when the sequence length reaches `2^n`. At this point, a final check is performed to ensure the circular condition (the first and last elements differ by one bit) is met. If so, a solution has been found.

```java
class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        result.add(start);
        visited.add(start);
        backtrack(n, (1 << n), result, visited);
        return result;
    }

    private boolean backtrack(int n, int totalSize, List<Integer> result, Set<Integer> visited) {
        if (result.size() == totalSize) {
            int first = result.get(0);
            int last = result.get(result.size() - 1);
            int xor = first ^ last;
            // Check if xor is a power of 2
            return (xor > 0) && ((xor & (xor - 1)) == 0);
        }

        int last = result.get(result.size() - 1);
        for (int i = 0; i < n; i++) {
            int next = last ^ (1 << i);
            if (!visited.contains(next)) {
                visited.add(next);
                result.add(next);
                if (backtrack(n, totalSize, result, visited)) {
                    return true;
                }
                // Backtrack
                visited.remove(next);
                result.remove(result.size() - 1);
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize a `result` list with `start`.
- Initialize a `visited` set with `start`.
- Define a recursive function `solve()`:
  - If `result.size() == 2^n`:
    - Check if `result.get(0)` and `result.get(result.size() - 1)` differ by one bit.
    - If they do, return `true`. Otherwise, return `false`.
  - Get `last = result.get(result.size() - 1)`.
  - For `i` from `0` to `n-1`:
    - Calculate `next = last ^ (1 << i)`.
    - If `next` is not in `visited`:
      - Add `next` to `result` and `visited`.
      - If `solve()` returns `true`, return `true`.
      - Backtrack: remove `next` from `result` and `visited`.
  - Return `false`.
- Call `solve()` to populate the `result` list.

## Generate and Rotate Standard Gray Code
This approach leverages the standard "reflected binary code" (a type of Gray code). First, it generates the standard sequence which starts at 0. Then, it finds the position of the given `start` element and rotates the sequence to make `start` the first element, preserving the circular permutation property.
**Time:** O(2^n). Generating the initial list takes `O(2^n)`. Finding the start index is part of the same loop. Creating the new rotated list takes another `O(2^n)`. · **Space:** O(2^n). We need to store the initial Gray code list and the final result list.
**Pros:** Much faster than backtracking, with a time complexity linear in the size of the output.; The logic is based on a well-known and reliable mathematical construction.
**Cons:** Requires `O(2^n)` auxiliary space for the initial Gray code list, in addition to the space for the final result.; Involves multiple passes over the data: one to generate, and another to create the rotated list.
### Explanation
The standard Gray code for an integer `i` can be computed using the formula `G(i) = i ^ (i >> 1)`. We begin by generating a list of all `2^n` Gray codes by applying this formula for `i` from `0` to `2^n - 1`. This gives a valid circular permutation that starts with `0`. Next, we iterate through this generated list to find the index of the `start` value. Once the `startIndex` is found, we perform a circular shift (rotation) on the list. The new list is constructed by taking the sublist from `startIndex` to the end, and appending the sublist from the beginning up to `startIndex`. The resulting list is a valid permutation because the original was circular, so the adjacency property is maintained even at the wrap-around point.

```java
class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        int size = 1 << n;
        List<Integer> grayCode = new ArrayList<>(size);
        int startIndex = 0;

        for (int i = 0; i < size; i++) {
            int code = i ^ (i >> 1);
            if (code == start) {
                startIndex = i;
            }
            grayCode.add(code);
        }

        List<Integer> result = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            result.add(grayCode.get((startIndex + i) % size));
        }
        return result;
    }
}
```
### Algorithm
- Create a list `grayCode`.
- Loop `i` from `0` to `2^n - 1`.
- Calculate the standard Gray code `g = i ^ (i >> 1)` and add it to `grayCode`.
- Find the index `startIndex` where `grayCode.get(startIndex) == start`.
- Create a `result` list.
- Add elements from `grayCode` from `startIndex` to the end into `result`.
- Add elements from `grayCode` from `0` to `startIndex - 1` into `result`.
- Return `result`.

## Direct Generation via Gray Code Property
This is the most efficient approach. It builds upon a key property of Gray codes: if a sequence is a Gray code, XORing every element with a constant value `C` produces another valid Gray code sequence. By choosing `C = start`, we can directly generate the desired sequence without any intermediate steps like rotation.
**Time:** O(2^n). The algorithm consists of a single loop that runs `2^n` times, with each iteration performing a few constant-time bitwise operations. · **Space:** O(2^n). This space is required to store the output list, which is unavoidable. No auxiliary space is needed.
**Pros:** Most efficient and elegant solution with the best constant factors.; Simple and concise to implement.; Generates the result directly in a single pass without needing intermediate data structures.
**Cons:** The underlying mathematical property might not be immediately obvious, making the solution seem like magic without the proper background knowledge.
### Explanation
Let `G = [g_0, g_1, ..., g_{m-1}]` be a standard Gray code sequence, where `m = 2^n`. This sequence is circular and `g_0 = 0`. A key property is that for any constant `C`, the sequence `P` where `p_i = g_i ^ C` is also a valid Gray code sequence. This is because the XOR difference between adjacent elements remains the same: `p_i ^ p_{i+1} = (g_i ^ C) ^ (g_{i+1} ^ C) = g_i ^ g_{i+1}`. Since `g_i` and `g_{i+1}` differ by one bit, so do `p_i` and `p_{i+1}`.

We want our sequence to start with the given `start` value. The standard sequence `G` starts with `g_0 = 0`. By choosing the constant `C = start`, the first element of our new sequence `P` becomes `p_0 = g_0 ^ start = 0 ^ start = start`. This gives us a direct formula to generate the `i`-th element of the result: `(i ^ (i >> 1)) ^ start`.

```java
class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        int size = 1 << n;
        List<Integer> result = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            // Standard Gray code for i is i ^ (i >> 1)
            // We XOR it with start to make the sequence begin with start
            result.add(start ^ i ^ (i >> 1));
        }
        return result;
    }
}
```
### Algorithm
- Create an empty `result` list.
- Loop `i` from `0` to `2^n - 1`.
- For each `i`, calculate the `i`-th standard Gray code: `gray_i = i ^ (i >> 1)`.
- Calculate the corresponding element in the desired permutation: `p_i = gray_i ^ start`.
- Add `p_i` to the `result` list.
- Return `result`.

# Solutions
### Java

```java
int gray ( x ) { return x ^ ( x >> 1 ); }
```

### CPP

```cpp
class Solution { public: vector < int > circularPermutation ( int n , int start ) { int g [ 1 << n ]; int j = 0 ; for ( int i = 0 ; i < 1 << n ; ++ i ) { g [ i ] = i ^ ( i >> 1 ); if ( g [ i ] == start ) { j = i ; } } vector < int > ans ; for ( int i = j ; i < j + ( 1 << n ); ++ i ) { ans . push_back ( g [ i % ( 1 << n )]); } return ans ; } };
```

### Python

```python
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]

```