Algorithm
Problem Name: 1238. Circular Permutation in Binary Representation
Problem Link: https://leetcode.com/problems/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] = startp[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 <= 160 <= start < 2 ^ n
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
class Solution:
def circularPermutation(self, n: int, start: int) -> List[int]:
return [start ^ i ^ i >> 1 for i in range(1 << n)]
Input
n = 2, start = 3
Output
[3,2,0,1]
#2 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _1238_CircularPermutationInBinaryRepresentation
{
public IList < int> CircularPermutation(int n, int start)
{
var result = new List<int>();
result.Add(start);
var queue = new Queue < int>();
queue.Enqueue(start);
var visited = new HashSet < int>() { start };
while (queue.Count > 0)
{
var temp = queue.Dequeue();
int mask = 1;
for (int i = 0; i < n; i++)
{
int m = mask << i;
int num = temp ^ m;
if (!visited.Contains(num))
{
queue.Enqueue(num);
visited.Add(num);
result.Add(num);
break;
}
}
}
return result;
}
}
}
Input
n = 2, start = 3
Output
[3,2,0,1]