Leetcode 1238: Circular Permutation in Binary Representation
Given two integers n and start, return a permutation of the integers from 0 to 2^n - 1 such that: p[0] = start, each pair of adjacent elements differ by exactly one bit in their binary representation, and p[0] and p[2^n - 1] also differ by exactly one bit.
Problem
Approach
Steps
Complexity
Input: You are given two integers n and start.
Example: n = 2, start = 3
Constraints:
• 1 <= n <= 16
• 0 <= start < 2^n
Output: Return a permutation p of integers from 0 to 2^n - 1 such that the required conditions are satisfied.
Example: [3, 2, 0, 1]
Constraints:
• The output should be a permutation of length 2^n.
Goal: Generate a valid permutation where adjacent numbers differ by one bit.
Steps:
• Loop through all possible numbers from 0 to 2^n - 1.
• For each number, calculate the corresponding Gray code using the formula.
• Generate the permutation based on the Gray code while ensuring that adjacent numbers differ by exactly one bit.
Goal: The problem guarantees that n is between 1 and 16, and start is between 0 and 2^n - 1.
Steps:
• 1 <= n <= 16
• 0 <= start < 2^n
Assumptions:
• It is assumed that the generated permutation will be in the correct format, starting at the given 'start' value.
• Input: Input: n = 3, start = 2
• Explanation: The binary representations of the permutation are (010, 110, 111, 101, 100, 000, 001, 011).
Approach: We can generate a circular permutation using Gray code, which ensures that adjacent elements differ by only one bit.
Observations:
• Gray code is a binary numeral system where two successive values differ in only one bit.
• This problem can be efficiently solved by generating the Gray code sequence for the range 0 to 2^n - 1.
Steps:
• Start with the given start value.
• Generate the Gray code for each integer from 0 to 2^n - 1.
• Ensure that the sequence starts at the given start and ends in a valid manner, differing by exactly one bit from the first element.
Empty Inputs:
• Not applicable since n and start are always defined.
Large Inputs:
• The largest possible value for n is 16, resulting in a permutation of length 65536.
Special Values:
• When start is 0 or 2^n - 1, ensure that the permutation starts and ends with valid elements differing by one bit.
Constraints:
• Time and space complexities must be optimized for the upper bound of n.
vector<int> circularPermutation(int n, int start) {
vector<int> res;
for(int i = 0; i < 1 << n; i++)
res.push_back(start ^ i ^ i >> 1);
return res;
}
1 : Function Definition
vector<int> circularPermutation(int n, int start) {
The function `circularPermutation` is defined to generate a circular permutation of `n` elements starting from the number `start`.
2 : Result Initialization
vector<int> res;
A vector `res` is initialized to store the resulting circular permutation.
3 : Loop Setup
for(int i = 0; i < 1 << n; i++)
A loop is set up to iterate over all possible values for the permutation. The loop runs from `0` to `2^n - 1` (i.e., `1 << n`).
4 : Gray Code Calculation
res.push_back(start ^ i ^ i >> 1);
The Gray code formula `start ^ i ^ (i >> 1)` is used to generate the next number in the circular permutation, and it is added to the result vector `res`.
5 : Return Result
return res;
The function returns the vector `res`, which contains the generated circular permutation.
Best Case: O(2^n)
Average Case: O(2^n)
Worst Case: O(2^n)
Description: The solution requires generating all 2^n elements in the permutation, each of which is processed once.
Best Case: O(2^n)
Worst Case: O(2^n)
Description: Space is required to store the output permutation of length 2^n.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus