problemmediumalgorithmsleetcode-1238leetcode 1238leetcode1238

Circular Permutation in Binary Representation

MediumUpdated: Jul 7, 2025
Practice on:
LeetCode

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

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

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

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Kotlin
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] }
    }
}
Python
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]
Rust
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()
    }
}
TypeScript
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)

Comments