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] 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.
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 ^ nProblem Overview: You need to generate a permutation of all 2^n integers represented with n bits such that adjacent numbers differ by exactly one bit. The sequence must also be circular, meaning the last and first numbers differ by one bit as well. The permutation must start with a given value start.
Approach 1: Gray Code Generation (Time: O(2^n), Space: O(2^n))
The key observation is that Gray code already produces a sequence where consecutive numbers differ by exactly one bit. The standard formula for the i-th Gray code is g = i ^ (i >> 1). This naturally generates a valid Hamiltonian cycle of the n‑bit hypercube, which satisfies the circular constraint. To make the sequence start with start, simply XOR every generated Gray code value with start. XOR preserves the one‑bit difference property because it applies the same transformation to all elements. Iterate from 0 to 2^n - 1, compute the Gray code, apply XOR with start, and append to the result list.
This approach leverages properties of bit manipulation and the mathematical structure of Gray codes. It avoids searching or validation because the sequence is guaranteed to satisfy the adjacency condition.
Approach 2: Backtracking with Validity Check (Time: O(2^n * n), Space: O(2^n))
Another way is to construct the permutation using backtracking. Treat each n‑bit number as a node in a graph where edges connect numbers whose XOR has exactly one set bit. Start from start, mark it as visited, and recursively try all numbers that differ by one bit and have not been used yet. Continue until the sequence contains all 2^n numbers. At the final step, verify that the last element differs from the starting element by one bit to satisfy the circular condition.
This approach explicitly explores the solution space using backtracking. Each step flips one bit of the current number to generate candidates, then checks if the candidate has already been used. While slower than the Gray code method, it demonstrates how the problem maps to a Hamiltonian path search on the n‑bit graph, which is a useful insight for problems involving bit states and math properties of binary representations.
Recommended for interviews: The Gray code approach is the expected solution. It runs in O(2^n) time with simple bit operations and directly guarantees the one‑bit adjacency property. Backtracking proves you understand the underlying graph structure, but interviewers typically prefer the Gray code insight because it is both optimal and elegant.
The problem can be closely linked to generating a Gray code sequence, where each number differs by one bit from the previous one.
To leverage this property, we first generate a Gray code sequence, then rotate it such that it starts with the specified number. The crux is understanding the bit manipulation involved in generating a Gray code: the n-th Gray code is derived by the formula G(i) = i ^ (i >> 1).
This C solution generates a full Gray code sequence first, determines where the given start element is in that sequence, then shifts the sequence such that it starts with the given element.
Time Complexity: O(2^n), as we generate exactly 2^n Gray codes.
Space Complexity: O(2^n), requiring space for the permutation array.
This approach involves using backtracking to generate permutations manually, ensuring at each point that adjacent elements differ by one bit. This allows us to test permutations and backtrack if a permutation does not hold the adjacency condition.
While not as straightforward as generating Gray code, this method can help in understanding permutations with constraints more deeply.
The C solution employs a backtracking approach to build the permutation sequence. At each step, it checks if the potential addition to the sequence maintains the one-bit difference constraint before moving forward in the recursion.
Time Complexity: Potentially O((2^n)!) in the worst scenario with exhaustive checking, but optimized by constraints.
Space Complexity: O(2^n) for result storage and used-tracking array.
| Approach | Complexity |
|---|---|
| Gray Code Generation | Time Complexity: O(2^n), as we generate exactly 2^n Gray codes. |
| Backtracking with Validity Check | Time Complexity: Potentially O((2^n)!) in the worst scenario with exhaustive checking, but optimized by constraints. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Gray Code Generation | O(2^n) | O(2^n) | Best approach. Directly constructs a valid circular permutation using Gray code properties. |
| Backtracking with Validity Check | O(2^n * n) | O(2^n) | Useful for understanding the graph structure of n-bit states or when deriving Gray code is not obvious. |
Leetcode 1238: Circular Permutation in Binary Representation • Algorithms Casts • 1,389 views views
Watch 9 more video solutions →Practice Circular Permutation in Binary Representation with our built-in code editor and test cases.
Practice on FleetCode