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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Circular Permutation in Binary Representation

Difficulty: Medium

Problem Description

Given 2 integers n and start. Your task is to return any permutation p of (0,1,2.....,2^n -1) such that:

  • p[0] = start
  • p[i] and p[i+1] differ by only one bit in their binary representation.
  • p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

Key Insights

  • The goal is to generate a circular Gray code sequence.
  • Gray codes are binary sequences where two consecutive values differ in exactly one bit.
  • Starting at a specified value (start) allows flexibility in generating the sequence.
  • The total number of values in the sequence is 2^n, where n defines the number of bits.

Space and Time Complexity

Time Complexity: O(2^n)
Space Complexity: O(1) (excluding the output)

Solution

To solve this problem, we can use the properties of Gray codes. A Gray code for n bits can be generated using the formula: G(i) = i ^ (i >> 1), where i ranges from 0 to 2^n - 1. After generating the full Gray code sequence, we can rotate it so that it starts at the specified start value. This ensures that the first element is start, and the properties of the Gray code guarantee that each pair of consecutive values (including the wrap-around) differ by exactly one bit.

Code Solutions

def circularPermutation(n: int, start: int) -> List[int]:
    # Generate the Gray code sequence
    gray_code = [(i ^ (i >> 1)) for i in range(1 << n)]
    # Find the index of the start value
    start_index = gray_code.index(start)
    # Rotate the list to start from the start value
    return gray_code[start_index:] + gray_code[:start_index]
← Back to All Questions