Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1238.html
1238. Circular Permutation in Binary Representation (Medium)
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]
andp[i+1]
differ by only one bit in their binary representation.p[0]
andp[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
Related Topics:
Math
Solution 1. Gray Code
// OJ: https://leetcode.com/problems/circular-permutation-in-binary-representation/
// Time: O(2^N)
// Space: O(1)
// Ref: https://leetcode.com/problems/circular-permutation-in-binary-representation/discuss/414203/JavaC%2B%2BPython-4-line-Gray-Code
class Solution {
public:
vector<int> circularPermutation(int n, int start) {
vector<int> ans;
for (int i = 0; i < (1 << n); ++i) ans.push_back(start ^ i ^ (i >> 1));
return ans;
}
};
-
class Solution { public List<Integer> circularPermutation(int n, int start) { List<Integer> grayCodeList = new ArrayList<Integer>(); grayCodeList.add(0); grayCodeList.add(1); for (int i = 2; i <= n; i++) { int power2 = (int) Math.pow(2, i - 1); int size = grayCodeList.size(); for (int j = size - 1; j >= 0; j--) { int prevNum = grayCodeList.get(j); int curNum = prevNum + power2; grayCodeList.add(curNum); } } List<Integer> permutation = new ArrayList<Integer>(); int index = grayCodeList.indexOf(start); int size = grayCodeList.size(); for (int i = 0; i < size; i++) { permutation.add(grayCodeList.get(index)); index = (index + 1) % size; } return permutation; } } ############ class Solution { public List<Integer> circularPermutation(int n, int start) { List<Integer> ans = new ArrayList<>(); for (int i = 0; i < 1 << n; ++i) { ans.add(i ^ (i >> 1) ^ start); } return ans; } }
-
// OJ: https://leetcode.com/problems/circular-permutation-in-binary-representation/ // Time: O(2^N) // Space: O(1) // Ref: https://leetcode.com/problems/circular-permutation-in-binary-representation/discuss/414203/JavaC%2B%2BPython-4-line-Gray-Code class Solution { public: vector<int> circularPermutation(int n, int start) { vector<int> ans; for (int i = 0; i < (1 << n); ++i) ans.push_back(start ^ i ^ (i >> 1)); return ans; } };
-
# 1238. Circular Permutation in Binary Representation # https://leetcode.com/problems/circular-permutation-in-binary-representation/ class Solution: def circularPermutation(self, n: int, start: int) -> List[int]: return [start ^ i ^ i>>1 for i in range(1 << n)]
-
func circularPermutation(n int, start int) (ans []int) { for i := 0; i < 1<<n; i++ { ans = append(ans, i^(i>>1)^start) } return }
-
function circularPermutation(n: number, start: number): number[] { const ans: number[] = []; for (let i = 0; i < 1 << n; ++i) { ans.push(i ^ (i >> 1) ^ start); } return ans; }