Circular Permutation in Binary Representation #15 Most Asked
Medium
3 views
Topics:
Bit Manipulation
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
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the constraints on the integer 'n' and the 'start' value? What is the maximum possible value for 'n'?
- Is there a specific behavior expected if a circular sequence starting with 'start' is impossible to generate?
- For the difference of one bit, are we referring to Hamming distance of 1, meaning exactly one bit is flipped?
- If multiple circular sequences exist starting with 'start', is any valid sequence acceptable, or is there a preferred order or characteristic?
- Could 'start' be a value outside the range of 0 to 2^n - 1?
Brute Force Solution
Approach
The brute force method for this problem is like trying every possible arrangement of numbers until we find one that satisfies our specific rule. We generate all the possible orders and then check if each order follows the circular permutation rule.
Here's how the algorithm would work step-by-step:
- First, make a list of all possible orders you can arrange the numbers.
- Then, take the first arrangement from your list.
- Check if this arrangement is a valid circular permutation by comparing each number in the arrangement with the number that comes after it.
- Also check if the last number is a valid permutation from the first number.
- If the arrangement is valid, you've found a solution. If not, move on to the next arrangement in your list.
- Repeat this process until you either find a valid arrangement or you've checked every possible arrangement in your list.
Code Implementation
def circular_permutation_brute_force(number_bits): max_number = 2 ** number_bits all_possible_numbers = list(range(max_number)) def gray_code_check(sequence): for i in range(len(sequence) - 1): xor_result = sequence[i] ^ sequence[i + 1]
if bin(xor_result).count('1') != 1:
return False return True def find_circular_permutation(current_sequence, remaining_numbers): if not remaining_numbers: # Base case: all numbers are used
if gray_code_check(current_sequence) and bin(current_sequence[-1] ^ current_sequence[0]).count('1') == 1:
return current_sequence else: return None for i in range(len(remaining_numbers)): next_number = remaining_numbers[i] if not current_sequence or bin(current_sequence[-1] ^ next_number).count('1') == 1: # Ensure gray code property new_sequence = current_sequence + [next_number] new_remaining_numbers = remaining_numbers[:i] + remaining_numbers[i+1:] result = find_circular_permutation(new_sequence, new_remaining_numbers) if result: return result
return None # Iterate through possible starting numbers
for start_number in all_possible_numbers:
remaining_numbers = all_possible_numbers[:] remaining_numbers.remove(start_number) solution = find_circular_permutation([start_number], remaining_numbers)
if solution: return solution return []Big(O) Analysis
Time Complexity
O(n * n!) – The brute force approach involves generating all possible permutations of the n numbers, which takes O(n!) time. For each permutation, we iterate through the list of n numbers to verify if the adjacent numbers satisfy the circular permutation property. This check requires O(n) operations. Therefore, the overall time complexity becomes O(n * n!). This is because we generate n! permutations and for each we do O(n) work.
Space Complexity
O(N!) – The algorithm first generates all possible permutations of the input numbers. Generating all permutations for N numbers requires storing each permutation in a list. Since there are N! possible permutations, the space required to store all these permutations is proportional to N factorial. Therefore, the auxiliary space complexity is O(N!).
Optimal Solution
Approach
The efficient way to solve this problem is by leveraging a special sequence called Gray code. Gray code has the property that consecutive numbers differ by only one bit, which perfectly matches the problem's requirement for a circular permutation. We generate the Gray code sequence and then transform it to match the problem's specific start number.
Here's how the algorithm would work step-by-step:
- First, generate a Gray code sequence for the required number of bits. There's a trick to doing this quickly based on the previous numbers in the sequence.
- Then, find where the given start number is in the Gray code sequence we just made.
- Finally, rearrange the Gray code sequence so it starts with the given start number. Because it's a cycle, we simply shift it to the correct starting position.
Code Implementation
def circular_permutation(number_of_bits):
gray_code_sequence = [0]
# Build the sequence iteratively
for _ in range(number_of_bits):
reflected_sequence = gray_code_sequence[::-1]
# Prepend 1 to the reflected sequence
reflected_sequence_with_one = [(1 << (_)) | value for value in reflected_sequence]
# Combining the sequences
gray_code_sequence += reflected_sequence_with_one
return gray_code_sequence
Big(O) Analysis
Time Complexity
O(2^n) – Generating the Gray code sequence for n bits involves creating a sequence of 2^n numbers. Finding the start number within the generated Gray code sequence requires iterating through this sequence, taking O(2^n) time. Rearranging the Gray code sequence by shifting elements also takes O(2^n) time. Therefore, the overall time complexity is dominated by these operations on a sequence of length 2^n, resulting in O(2^n).
Space Complexity
O(2^n) – The algorithm generates a Gray code sequence of length 2^n, where n is the input representing the number of bits. This sequence is stored in a list or array, contributing O(2^n) space. Finding the start number and rearranging the sequence involve operations on this list, but don't create new data structures of significant size. Therefore, the dominant space complexity is due to storing the Gray code sequence itself, which is O(2^n).
Edge Cases
| Case | How to Handle |
|---|---|
| n is 0 | Return a list containing only the start value since 2^0 = 1 and the sequence must start with start. |
| n is a large value (e.g., n > 20) | Be mindful of integer overflow when calculating 2^n, potentially use a long or BigInteger if the language requires it. |
| start is negative (or outside the range [0, 2^n - 1]) | Take the absolute value modulo 2^n of the number to ensure it's within the appropriate range to obtain a value in the defined set, or explicitly throw an error if out of bounds is not permitted |
| start is equal to 2^n | Return to start modulus 2^n, to ensure value stays within the 0 to 2^n - 1 range or throw an exception if out of bounds is not permitted |
| When n is large enough that creating the entire sequence in memory is problematic | Consider an iterative solution which generates the next element on-demand rather than storing the entire list in memory at once, avoiding O(2^n) space complexity. |
| No valid solution exists because start is invalid. | Ensure start is a valid n-bit integer by checking if it falls between 0 and 2^n-1, throwing an error if out of range. |
| Integer overflow during Gray code calculation | Use appropriate data types (e.g., long in Java/C++) to avoid overflow when calculating Gray codes. |
| Algorithm incorrectly generates non-unique values | Verify that each generated number is unique by using a set or other mechanism to track used numbers to guarantee the sequence property. |
n is 0
How to Handle:
Return a list containing only the start value since 2^0 = 1 and the sequence must start with start.
n is a large value (e.g., n > 20)
How to Handle:
Be mindful of integer overflow when calculating 2^n, potentially use a long or BigInteger if the language requires it.
start is negative (or outside the range [0, 2^n - 1])
How to Handle:
Take the absolute value modulo 2^n of the number to ensure it's within the appropriate range to obtain a value in the defined set, or explicitly throw an error if out of bounds is not permitted
start is equal to 2^n
How to Handle:
Return to start modulus 2^n, to ensure value stays within the 0 to 2^n - 1 range or throw an exception if out of bounds is not permitted
When n is large enough that creating the entire sequence in memory is problematic
How to Handle:
Consider an iterative solution which generates the next element on-demand rather than storing the entire list in memory at once, avoiding O(2^n) space complexity.
No valid solution exists because start is invalid.
How to Handle:
Ensure start is a valid n-bit integer by checking if it falls between 0 and 2^n-1, throwing an error if out of range.
Integer overflow during Gray code calculation
How to Handle:
Use appropriate data types (e.g., long in Java/C++) to avoid overflow when calculating Gray codes.
Algorithm incorrectly generates non-unique values
How to Handle:
Verify that each generated number is unique by using a set or other mechanism to track used numbers to guarantee the sequence property.
0/0 Walmart questions completed
0/0 completed
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
