1238. Circular Permutation in Binary Representation
Problem Description
The problem gives us two integers n
and start
. It asks us to generate a permutation p
of the sequence of numbers from 0 to 2^n - 1
, subject to the following conditions:
- The first element in the permutation
p
must bestart
. - Any two consecutive elements in
p
(i.e.p[i]
andp[i+1]
) must differ by only one bit in their binary representation. This property is also known as being adjacent in the context of a Gray code sequence. - Additionally, the first and last elements of the permutation (
p[0]
andp[2^n - 1]
) must also differ by only one bit. Essentially, this should be a circular sequence where you can loop from the end back to the beginning seamlessly, maintaining the one-bit difference property.
The task is to return any such valid permutation that satisfies these criteria.
Flowchart Walkthrough
Let's analyze the problem using the Flowchart to determine the appropriate solution strategy for LeetCode problem 1238, Circular Permutation in Binary Representation:
-
Is it a graph?
- No: This problem does not inherently involve nodes and edges as typical graph problems do.
-
Need to solve for kth smallest/largest?
- No: The objective is not about finding the kth smallest or largest element.
-
Involves Linked Lists?
- No: The challenge does not involve any operations with linked lists.
-
Does the problem have small constraints?
- Yes: The problem size is defined by
n
, representing the number of bits, which typically suggest smaller constraints since the size of permutations grows exponentially but remains manageable for computational handling.
- Yes: The problem size is defined by
-
Brute force / Backtracking?
- Yes: Given the small constraints and the problem's nature of exploring permutations and combinations where each number differs by only one bit, brute force or backtracking is effective for exploring all possible configurations to meet the specific condition.
Conclusion: Based on the flowchart, a backtracking or brute force algorithm is indicated to generate all permutations of numbers in the binary format where every adjacent number differs by exactly one bit. This systematic approach helps to efficiently explore possible solutions respecting the problem's constraints.
Intuition
To solve this problem, knowledge of the Gray code is quite useful. Gray code is a binary numeral system where two successive numbers differ in only one bit. It's a perfect fit for our problem requirements.
To generate a sequence of Gray code for n bits, we start with a sequence for n-1
bits then:
- We prefix the original sequence with
0
to keep the numbers as they are. - Then we take the reversed sequence of
n-1
bits and prefix it with1
, which will flip the most significant bit of those numbers. - Finally, we concatenate these two lists into one, which will satisfy the condition that each adjacent number differs by one bit.
However, in this problem, we need to start at a specific number (start
), and also the sequence should be circular (the start and end elements should differ by only one bit).
We can achieve this by noting that XOR operation between a number and 1
will flip the last bit. Given a number i
, i XOR (i >> 1)
will give us the Gray code for i
. If we further XOR this with start
, we effectively rotate the Gray code sequence to start at start
because XOR operation with a number itself cancels out (is 0), while XOR with 0 keeps the number unchanged.
By using the formula i XOR (i >> 1) XOR start
we can generate a sequence starting from start
and ensure that the first and last numbers are also one bit apart, satisfying the circular condition:
- We create a list with a size of
2^n
to hold our permutation. - For each number
i
from0
to2^n - 1
, we apply the formula to generate the sequence. The>>
is a right shift bitwise operator, which divides the number by two (or removes the last bit). - The resulting list is the desired permutation meeting all problem conditions.
Learn more about Math and Backtracking patterns.
Solution Approach
The implementation of the solution leverages a simple yet clever use of bitwise operations to generate the desired permutation list. The solution does not explicitly construct Gray codes; instead, it uses a known property of Gray codes, which is that the binary representation of the i
th Gray code is i XOR (i >> 1)
. Here's a step-by-step of how the algorithm in the reference solution works:
-
The size of the output permutation list will be
2^n
. This is because we want to include all numbers from0
to2^n - 1
inclusive. -
The core of the reference solution relies on list comprehension in Python, which is an elegant and compact way of generating lists.
-
Inside the list comprehension, for every integer
i
in the range0
to2^n - 1
, the Gray code equivalent is computed asi XOR (i >> 1)
. This leverages the bitwise XOR operator^
and right shift operator>>
. The right shift operator effectively divides the number by two or in binary terms, shifts all bits to the right, dropping the least significant bit. -
Having computed the Gray code equivalent, it is further XORed with
start
. This ensures that our permutation will start at the givenstart
value. If our Gray code was zero-based, this step essentially "rotates" the Gray code sequence so that thestart
value becomes the first in the sequence. This step is critical because it satisfies the requirement thatp[0]
must be equal tostart
. -
The list comprehension ultimately constructs the permutation list, with each element now satisfying the property that any two consecutive elements will differ by exactly one bit.
Here's the actual line of Python code responsible for creating the permutation:
1return [i ^ (i >> 1) ^ start for i in range(1 << n)]
In this line of code, (1 << n)
is equivalent to 2^n
, meaning the range
function generates all numbers from 0
to 2^n - 1
. The algorithm does not require additional data structures other than the list that it returns, making it space-efficient.
This approach combines knowledge of Gray codes with simple bitwise manipulation in Python to meet all problem requirements efficiently. The resulting algorithm runs in linear time relative to the size of the output list, which is O(2^n), since it must touch each entry in the permutation exactly once.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example using the solution approach where n = 2
and start = 3
. The sequence we want to generate will have 2^n = 4
elements, and they are permutations of [0, 1, 2, 3]
. We want p[0]
to be 3
, and every consecutive element should differ by one bit, including the last element and the first.
Step-by-step process:
-
We calculate the size of the output array, which will be
2^2 = 4
. -
We know that we must start with
start
, which is3
in this case, i.e.,p[0] = 3
. -
Now, we iterate from
i = 0
toi = 3
and apply the transformationi XOR (i >> 1) XOR start
to find the rest of the sequence. -
Let's perform the iterations:
- For
i = 0
: Gray code is0 XOR (0 >> 1) = 0
. We then XOR withstart
:0 XOR 3 = 3
. Our sequence is[3]
. - For
i = 1
: Gray code is1 XOR (1 >> 1) = 1 XOR 0 = 1
. XOR withstart
:1 XOR 3 = 2
. The sequence becomes[3, 2]
. - For
i = 2
: Gray code is2 XOR (2 >> 1) = 2 XOR 1 = 3
. XOR withstart
:3 XOR 3 = 0
. The sequence updates to[3, 2, 0]
. - For
i = 3
: Gray code is3 XOR (3 >> 1) = 3 XOR 1 = 2
. XOR withstart
:2 XOR 3 = 1
. The final sequence is[3, 2, 0, 1]
.
- For
Each element of this sequence differs by exactly one bit from the next, which you can verify by checking the binary representations: 11 (3)
, 10 (2)
, 00 (0)
, 01 (1)
. Also note that the first and last elements (3
and 1
respectively) differ by one bit (11
to 01
), so we have a circular sequence.
Hence, for n = 2
, start = 3
, our example has shown that the permutation generated by this approach is [3, 2, 0, 1]
. This permutation is a valid solution to the problem.
Solution Implementation
1from typing import List
2
3class Solution:
4 def circularPermutation(self, n: int, start: int) -> List[int]:
5 # Create a list of Gray codes with a transformation for circular permutation
6 # n: int - The number of digits in the binary representation of the list elements.
7 # start: int - The value at which the circular permutation will begin.
8 # return: List[int] - The resulting list of circularly permuted Gray codes.
9
10 # Calculate 2^n to determine the total number of elements in the permutation
11 total_numbers = 1 << n
12
13 # Generate the list of circularly permuted Gray codes
14 circular_perm = [self.grayCode(i) ^ start for i in range(total_numbers)]
15
16 return circular_perm
17
18 def grayCode(self, number: int) -> int:
19 # Convert a binary number to its Gray code equivalent
20 # number: int - The binary number to convert.
21 # return: int - The Gray code of the input number.
22
23 return number ^ (number >> 1)
24
25# Example usage:
26# Instantiate the Solution class and call the circularPermutation method
27sol = Solution()
28# Replace 'n' and 'start' with your specific values
29permutation = sol.circularPermutation(n, start)
30print(permutation)
31
1class Solution {
2 // Method to generate and return a list of integers representing a circular permutation in binary representation
3 public List<Integer> circularPermutation(int n, int start) {
4 // Initialize a list to store the circular permutation result
5 List<Integer> answer = new ArrayList<>();
6
7 // Loop to generate all possible binary numbers of n digits
8 for (int i = 0; i < (1 << n); ++i) {
9 // Generate the i-th Gray code by XORing i with itself right-shifted by 1 bit
10 int grayCode = i ^ (i >> 1);
11 // XOR the Gray code with the start value to get the circular permutation
12 int permutation = grayCode ^ start;
13 // Add the permutation to the list
14 answer.add(permutation);
15 }
16
17 // Return the finished list of permutations
18 return answer;
19 }
20}
21
1#include <vector> // Include the vector header for using the std::vector
2
3class Solution {
4public:
5 // Function to generate a circular permutation of size 2^n starting from 'start'.
6 std::vector<int> circularPermutation(int n, int start) {
7 // Create a vector to hold the numbers of the permutation
8 std::vector<int> permutation(1 << n); // 1 << n is equivalent to 2^n
9
10 // Fill the permutation vector using Gray code logic and applying the start offset.
11 for (int i = 0; i < (1 << n); ++i) {
12 // Calculate the i-th Gray code by XORing i with its right-shifted self.
13 int grayCode = i ^ (i >> 1);
14
15 // XOR with 'start' to rotate the permutation so that it begins with 'start'.
16 permutation[i] = grayCode ^ start;
17 }
18
19 // Return the resulting circular permutation vector.
20 return permutation;
21 }
22};
23
1// Generates a circular permutation of binary numbers of length n, starting from a given number.
2// The approach creates a Gray code sequence and applies bitwise XOR with the start value.
3function circularPermutation(n: number, start: number): number[] {
4 // Initialize the answer array to hold the circular permutation sequence.
5 const permutation: number[] = [];
6
7 // 1 << n computes 2^n, which is the total number of binary numbers possible with n bits.
8 // Iterate over the range to generate the sequence.
9 for (let index = 0; index < (1 << n); ++index) {
10 // Calculate the Gray code for the current index. In Gray code,
11 // two successive values differ in only one bit.
12 // Then apply the XOR operation with the start value to rotate the sequence
13 // such that it begins with 'start'.
14 const grayCode = index ^ (index >> 1) ^ start;
15
16 // Append the calculated value to the permutation array.
17 permutation.push(grayCode);
18 }
19
20 // Return the constructed circular permutation array.
21 return permutation;
22}
23
Time and Space Complexity
Time Complexity
The time complexity of the given code is based on the number of elements generated for the circular permutation. Since the code generates a list of size 2^n
(as indicated by 1 << n
which is equivalent to 2^n
), iterating through all these elements once, the time complexity is O(2^n)
.
Space Complexity
The space complexity is also O(2^n)
since a new list of size 2^n
is being created and returned. No additional space that scales with n
is used, so the space complexity is directly proportional to the output size.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.