Scale Engineer

Circular Permutation in Binary Representation

Med
#1156Time: O(n * 2^n). The recursion can have a depth of `2^n`. At each step, we explore up to `n` possible next elements by flipping each bit of the current number.Space: O(2^n). This space is used for the recursion stack (which can go up to `2^n` deep), the `visited` set, and the `result` list.
Patterns
MathBacktrackingBit Manipulation

Prompt

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1) such that :

  • p[0] = start
  • p[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 <= 16
  • 0 <= start < 2 ^ n

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a classic backtracking algorithm to explore all possible permutations. It builds the sequence one number at a time, ensuring each new number satisfies the single-bit-difference rule. If it reaches a dead end, it backtracks to try another path. This is conceptually a search for a Hamiltonian Path in an n-dimensional hypercube graph.

Algorithm

  • Initialize a result list with start.
  • Initialize a visited set with start.
  • Define a recursive function solve():
    • If result.size() == 2^n:
      • Check if result.get(0) and result.get(result.size() - 1) differ by one bit.
      • If they do, return true. Otherwise, return false.
    • Get last = result.get(result.size() - 1).
    • For i from 0 to n-1:
      • Calculate next = last ^ (1 << i).
      • If next is not in visited:
        • Add next to result and visited.
        • If solve() returns true, return true.
        • Backtrack: remove next from result and visited.
    • Return false.
  • Call solve() to populate the result list.

Walkthrough

The algorithm starts with a list containing only the start element. A visited set is used to keep track of numbers that are already part of the sequence to avoid cycles and redundant computations. A recursive function is defined to build the permutation. In each recursive call, it takes the last element added to the sequence and tries to find a valid next element by flipping each of its n bits one by one. A candidate is valid if it hasn't been visited yet. If a valid candidate is found, it's added to the sequence, and the function calls itself. If the recursive call fails to find a complete path, the candidate is removed (this is the backtracking step). The base case for the recursion is when the sequence length reaches 2^n. At this point, a final check is performed to ensure the circular condition (the first and last elements differ by one bit) is met. If so, a solution has been found.

class Solution {    public List<Integer> circularPermutation(int n, int start) {        List<Integer> result = new ArrayList<>();        Set<Integer> visited = new HashSet<>();        result.add(start);        visited.add(start);        backtrack(n, (1 << n), result, visited);        return result;    }     private boolean backtrack(int n, int totalSize, List<Integer> result, Set<Integer> visited) {        if (result.size() == totalSize) {            int first = result.get(0);            int last = result.get(result.size() - 1);            int xor = first ^ last;            // Check if xor is a power of 2            return (xor > 0) && ((xor & (xor - 1)) == 0);        }         int last = result.get(result.size() - 1);        for (int i = 0; i < n; i++) {            int next = last ^ (1 << i);            if (!visited.contains(next)) {                visited.add(next);                result.add(next);                if (backtrack(n, totalSize, result, visited)) {                    return true;                }                // Backtrack                visited.remove(next);                result.remove(result.size() - 1);            }        }        return false;    }}

Complexity

Time

O(n * 2^n). The recursion can have a depth of `2^n`. At each step, we explore up to `n` possible next elements by flipping each bit of the current number.

Space

O(2^n). This space is used for the recursion stack (which can go up to `2^n` deep), the `visited` set, and the `result` list.

Trade-offs

Pros

  • It's a general approach for path-finding problems and is guaranteed to find a solution if one exists.

  • Conceptually straightforward for those familiar with recursion and backtracking.

Cons

  • Significantly slower than other approaches due to its exponential nature.

  • May result in a 'Time Limit Exceeded' error for larger values of n (e.g., n=16).

Solutions

int gray ( x ) { return x ^ ( x >> 1 ); }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem