Domain 2MediumMEDIUM

Circular Permutation in Binary Representation

Construct a circular Gray code sequence starting from 'start' by generating the standard Binary Reflected Gray Code and rotating it to align with the required start value.

Domain: medium•Updated: 2026-09-11
#Gray Code#Bit Manipulation#O(2^n) Time#O(2^n) Space

Problem Breakdown

We need to construct a permutation of integers [0,1,…,2n−1][0, 1, \dots, 2^n - 1] such that adjacent elements differ by exactly one bit (Hamming distance = 1). Additionally, the sequence must be circular: p[n] and start (p[0]) also satisfy this condition.

  • Input: Integers n (1≤n≤161 \le n \le 16) and start.
  • Output: A list of integers representing the permutation.
  • Key Constraint: The sequence must be a valid Gray Code cycle, rotated so that it begins at start.

Intuition

A naive backtracking approach (DFS/BFS) to find any path visiting every node exactly once is inefficient (O(2n⋅n!)O(2^n \cdot n!) or worse without structure). However, the problem describes properties of a Binary Reflected Gray Code.

  1. The formula g(i)=i⊕(i>>1)g(i) = i \oplus (i >> 1) generates a sequence where consecutive values differ by one bit.
  2. Crucially, this standard generation forms a cycle: the last element differs from the first by exactly one bit.
  3. Since every number in range [0,2n−1][0, 2^n - 1] appears exactly once in this generated list, we can simply generate the full sequence starting at 0 and rotate it so that start becomes the head of the array.

Approach

  1. Generate Standard Sequence: Create a list using the Gray Code formula g(i)=i⊕(i>>1)g(i) = i \oplus (i >> 1) for all integers ii from 00 to 2n−12^n - 1. This ensures adjacency constraints are met globally and circularly.
  2. Locate Start Value: Find the index of start within this generated list using a linear search (list.index()). Since Gray Codes contain unique values, this is guaranteed to succeed given valid inputs.
  3. Rotate List: Use Python slicing to rotate the array: take elements from index to end and append elements from start up to index. This operation preserves adjacency because it’s a cyclic shift of an already valid cycle.

Complexity Analysis

  • Time Complexity: O(2n)O(2^n).
    • Generating the list iterates through all possible values (00 to 2n−12^n-1), performing constant-time bitwise operations per iteration.
    • Finding start takes linear time relative to the list size, which is dominated by generation overhead anyway (or can be considered part of processing).
    • Slicing and concatenating creates a new list proportional to output size O(2n)O(2^n).
  • Space Complexity: O(2n)O(2^n) for storing the permutation. This is optimal as we must return an array of this specific length. Auxiliary space used by variables is minimal (O(1)O(1)).

Solution

from typing import List

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        # Generate the standard Binary Reflected Gray Code sequence starting at 0.
        # The formula g(i) = i ^ (i >> 1) ensures that consecutive values 
        # in this list differ by exactly one bit and cover all numbers from 0 to 2^n - 1.
        perm = [i ^ (i >> 1) for i in range(2 ** n)]
        
        # Find the index where our required 'start' value appears in the generated sequence.
        idx = perm.index(start)
        
        # Rotate the list so that 'start' becomes the first element.
        # This preserves the circular adjacency property because it's a cyclic shift 
        # of an already valid Gray Code cycle.
        return perm[idx:] + perm[:idx]

Edge Cases Handled

  • n = 1: The loop runs for range(2), generating [0, 1]. If start is 0 or 1, the rotation correctly returns a valid list of size 2.
  • start = 0: idx will be 0 (since standard Gray Code starts at 0). The slice logic [perm[0:]] + perm[:0] simply returns the generated list unchanged, which is correct.
  • Large n (up to 16): Python handles integers of arbitrary size automatically; bitwise operations are efficient (O(1)O(1) relative to bit width for fixed machine words). The memory footprint scales linearly with 2n2^n, fitting within standard limits for competitive programming environments at n=16n=16.
  • start = max value: If start is the last element in a Gray Code cycle, slicing handles wrapping correctly (e.g., if index is 3 and size is 4, it returns [perm[3]] + [perm[0], perm[1], perm[2]]).