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 be start.
Any two consecutive elements in p (i.e. p[i] and p[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] and p[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.
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 with 1, 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 from 0 to 2^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 ith 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 from 0 to 2^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 range 0 to 2^n - 1, the Gray code equivalent is computed as i 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 given start value. If our Gray code was zero-based, this step essentially "rotates" the Gray code sequence so that the start value becomes the first in the sequence. This step is critical because it satisfies the requirement that p[0] must be equal to start.
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:

return [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 Evaluator

Example 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 is 3 in this case, i.e., p[0] = 3.
Now, we iterate from i = 0 to i = 3 and apply the transformation i XOR (i >> 1) XOR start to find the rest of the sequence.
Let's perform the iterations:
- For i = 0: Gray code is 0 XOR (0 >> 1) = 0. We then XOR with start: 0 XOR 3 = 3. Our sequence is [3].
- For i = 1: Gray code is 1 XOR (1 >> 1) = 1 XOR 0 = 1. XOR with start: 1 XOR 3 = 2. The sequence becomes [3, 2].
- For i = 2: Gray code is 2 XOR (2 >> 1) = 2 XOR 1 = 3. XOR with start: 3 XOR 3 = 0. The sequence updates to [3, 2, 0].
- For i = 3: Gray code is 3 XOR (3 >> 1) = 3 XOR 1 = 2. XOR with start: 2 XOR 3 = 1. The final sequence is [3, 2, 0, 1].

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know