We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Circular Permutation in Binary Representation

Number: 1359

Difficulty: Medium

Paid? No

Companies: Walmart Labs

Problem Description

Given two integers n and start, generate any permutation p of the numbers in the range [0, 2^n - 1] such that:

  • p[0] equals start.
  • Every successive pair of elements in p differ by exactly one bit in their binary representation.
  • Additionally, p[0] and p[2^n - 1] also differ by exactly one bit.

Key Insights

  • The problem is essentially about generating a Gray code sequence.
  • A standard Gray code for n bits can be generated using the formula: number i is transformed into i ^ (i >> 1).
  • The Gray code sequence inherently guarantees that consecutive numbers differ by one bit.
  • Because the Gray code sequence is circular, we can simply rotate the sequence so that the sequence starts with the given number "start".

Space and Time Complexity

Time Complexity: O(2^n) – We generate 2^n numbers. Space Complexity: O(2^n) – A list of 2^n elements is stored.

Solution

The solution leverages the intrinsic properties of the Gray code sequence. First, we generate the Gray code sequence using the formula i ^ (i >> 1) for all values from 0 to 2^n - 1. Next, we locate the index where the generated Gray code equals the given "start" value. Finally, we rotate the sequence so that it begins with "start". The circular nature of Gray code ensures that the adjacent differences, including the gap between the last and first elements, remain one-bit differences.

Code Solutions

# Python solution with detailed comments

def circularPermutation(n: int, start: int):
    # Calculate total number of elements in the Gray code sequence
    total_numbers = 1 << n  # equivalent to 2^n

    # Generate standard Gray code sequence using formula: gray = i ^ (i >> 1)
    gray_code = [i ^ (i >> 1) for i in range(total_numbers)]
    
    # Find the index at which the sequence equals the starting number
    start_index = gray_code.index(start)
    
    # Rotate the gray_code sequence so that it starts from 'start'
    rotated_gray_code = gray_code[start_index:] + gray_code[:start_index]
    
    return rotated_gray_code

# Example usage:
print(circularPermutation(2, 3))  # Expected output: [3,2,0,1] or another valid permutation
← Back to All Questions