1238. Circular Permutation in Binary Representation
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> circularPermutation(int n, int start) {
deque<int> res {0};
int p = 1;
while(res.size() < (1<<n)) {
int sz = res.size();
for(int i = sz - 1; i >= 0; i--) {
res.push_back(res[i] | p);
}
p<<=1;
}
while(res.front() != start) {
res.push_back(res.front());
res.pop_front();
}
return vector<int>(begin(res), end(res));
}
};
|
