Circular Permutation in Binary Representation
Problem
Given integers n and start, return any permutation p of the integers in the range [0, 2n − 1] such that p[0] = start, every pair of adjacent elements differs by exactly one bit, and the first and last elements also differ by exactly one bit (the sequence is circular).
n = 2, start = 3[3, 2, 0, 1]def circular_permutation(n, start):
result = []
for i in range(1 << n):
gray = i ^ (i >> 1)
result.append(start ^ gray)
return resultfunction circularPermutation(n, start) {
const result = [];
for (let i = 0; i < (1 << n); i++) {
const gray = i ^ (i >> 1);
result.push(start ^ gray);
}
return result;
}class Solution {
public List<Integer> circularPermutation(int n, int start) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < (1 << n); i++) {
int gray = i ^ (i >> 1);
result.add(start ^ gray);
}
return result;
}
}vector<int> circularPermutation(int n, int start) {
vector<int> result;
for (int i = 0; i < (1 << n); i++) {
int gray = i ^ (i >> 1);
result.push_back(start ^ gray);
}
return result;
}Explanation
We must list all numbers from 0 to 2ⁿ - 1 in an order where each neighbour (including the wrap-around) differs by exactly one bit, beginning at start. There's a famous sequence that already has this property: Gray code.
The Gray code of i is computed instantly as gray = i ^ (i >> 1). Listing gray(0), gray(1), gray(2), ... gives a cyclic ordering of all n-bit numbers where consecutive entries flip a single bit — exactly the adjacency rule the problem wants.
The only twist is starting at start instead of 0. XOR-ing every value by the same constant preserves the "differ by one bit" relationship (it just relabels the bits consistently), and it sends the first entry gray(0) = 0 to start ^ 0 = start. So we output start ^ gray(i) for each i.
Example: n = 2, start = 3. The Gray sequence is 0, 1, 3, 2; XOR each with 3 to get 3, 2, 0, 1. Every neighbour flips one bit and the list closes back to 3.