Circular Permutation in Binary Representation - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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.
Approach 1: Gray Code Generation
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.
Complexity
Time Complexity: O(2^n), as we generate exactly 2^n Gray codes.
Space Complexity: O(2^n), requiring space for the permutation array.
Approach 2: Backtracking with Validity Check
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.
Complexity
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 3: Binary Code to Gray Code
We observe the arrangement in the problem, and find that in its binary representation, only one bit is different between any two (including the first and last) adjacent numbers. This kind of coding method is Gray code, which is a coding method we will encounter in engineering.
The rule for converting binary code to binary Gray code is to keep the highest bit of the binary code as the highest bit of the Gray code, and the second highest bit of the Gray code is the XOR of the highest bit and the second highest bit of the binary code. The rest of the Gray code is similar to the second highest bit.
Assume a binary number is represented as B_{n-1}B_{n-2}...B_2B_1B_0, its Gray code representation is G_{n-1}G_{n-2}...G_2G_1G_0. The highest bit is kept, so G_{n-1} = B_{n-1}; and the other bits G_i = B_{i+1} \oplus B_{i}, where i=0,1,2..,n-2.
Therefore, for an integer x, we can use the function gray(x) to get its Gray code:
int gray(x) {
return x ^ (x >> 1);
}
We can directly convert the integers [0,..2^n - 1] into the corresponding Gray code array, then find the position of start in the Gray code array, cut the Gray code array from this position, and then append the cut part to the front of the Gray code array to get the arrangement required by the problem.
The time complexity is O(2^n), and the space complexity is O(2^n). Where n is the integer given in the problem.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Conversion Optimization
Since gray(0) = 0, then gray(0) \oplus start = start, and gray(i) is only one binary bit different from gray(i-1), so gray(i) \oplus start is also only one binary bit different from gray(i-1) \oplus start.
Therefore, we can also directly convert the integers [0,..2^n - 1] into the corresponding gray(i) \oplus start to get the Gray code arrangement with start as the first term.
The time complexity is O(2^n), where n is the integer given in the problem. Ignoring the space consumption of the answer, the space complexity is O(1).
Complexity Comparison
| 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. |
| Binary Code to Gray Code | — |
| Conversion Optimization | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Leetcode 1238: Circular Permutation in Binary Representation • Algorithms Casts • 1,401 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Circular Permutation in Binary Representation easy or hard?
Circular Permutation in Binary Representation Python or Java solution
How to solve Circular Permutation in Binary Representation in O(2^n)?
What is the best approach for Circular Permutation in Binary Representation?
Is Circular Permutation in Binary Representation asked at Google Amazon Meta?
What data structure is used in Circular Permutation in Binary Representation?
What is the time complexity of Circular Permutation in Binary Representation?
Ready to solve this problem?
Practice Circular Permutation in Binary Representation with our built-in code editor and test cases.
Practice on FleetCode