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.

Examples

Example 1

1
2
3
4

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

1
2
3

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

Solution

Method 1 – Gray Code Construction

Intuition

A circular permutation where each adjacent number differs by one bit is exactly a Gray code sequence. By generating the standard Gray code and rotating it so that it starts with start, we get the required permutation.

Approach

  1. Generate the Gray code sequence for n bits: for each i in 0..2^n-1, the Gray code is i ^ (i >> 1).
  2. Find the index of start in the Gray code sequence.
  3. Rotate the sequence so that it starts with start.
  4. Return the rotated sequence.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    vector<int> circularPermutation(int n, int start) {
        int sz = 1 << n;
        vector<int> g(sz);
        for (int i = 0; i < sz; ++i) g[i] = i ^ (i >> 1);
        auto it = find(g.begin(), g.end(), start);
        rotate(g.begin(), it, g.end());
        return g;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func circularPermutation(n int, start int) []int {
    sz := 1 << n
    g := make([]int, sz)
    for i := 0; i < sz; i++ {
        g[i] = i ^ (i >> 1)
    }
    idx := 0
    for i, v := range g {
        if v == start {
            idx = i
            break
        }
    }
    ans := append(g[idx:], g[:idx]...)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        int sz = 1 << n;
        List<Integer> g = new ArrayList<>();
        for (int i = 0; i < sz; i++) g.add(i ^ (i >> 1));
        int idx = g.indexOf(start);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < sz; i++) ans.add(g.get((idx + i) % sz));
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun circularPermutation(n: Int, start: Int): List<Int> {
        val sz = 1 shl n
        val g = List(sz) { it xor (it shr 1) }
        val idx = g.indexOf(start)
        return List(sz) { g[(idx + it) % sz] }
    }
}
1
2
3
4
5
6

class Solution:
    def circularPermutation(self, n: int, start: int) -> list[int]:
        sz = 1 << n
        g = [i ^ (i >> 1) for i in range(sz)]
        idx = g.index(start)
        return g[idx:] + g[:idx]
1
2
3
4
5
6
7
8

impl Solution {
    pub fn circular_permutation(n: i32, start: i32) -> Vec<i32> {
        let sz = 1 << n;
        let mut g: Vec<i32> = (0..sz).map(|i| i ^ (i >> 1)).collect();
        let idx = g.iter().position(|&x| x == start).unwrap();
        g[idx..].iter().chain(g[..idx].iter()).cloned().collect()
    }
}
1
2
3
4
5
6
7
8

class Solution {
    circularPermutation(n: number, start: number): number[] {
        const sz = 1 << n;
        const g = Array.from({length: sz}, (_, i) => i ^ (i >> 1));
        const idx = g.indexOf(start);
        return g.slice(idx).concat(g.slice(0, idx));
    }
}

Complexity

  • ⏰ Time complexity: O(2^n)
  • 🧺 Space complexity: O(2^n)