Circular Permutation in Binary Representation

Medium Bit Manipulation Tricks to remember Original on LeetCode

Circular Permutation in Binary Representation is a medium bit manipulation problem solved with the tricks to remember pattern. The best approach, optimal (gray code xor start), runs in O(2^n) time and O(1) extra space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking) up.

Problem

Given an integer n and a value start with 0 <= start < 2^n, return an ordering of all the numbers 0, 1, …, 2^n - 1, each exactly once, such that:

  • the first number is start;
  • every two neighbouring numbers differ in exactly one bit of their binary form;
  • the last number and the first number also differ in exactly one bit, so the ordering works as a circle.

Any ordering that meets these rules is accepted.

Examples

Example 1

Input
n = 2, start = 1
Output
[1, 0, 2, 3]
Why
In binary: 01, 00, 10, 11. Each neighbour pair differs in one bit, and so do 11 and 01 at the wrap-around. Other valid orders are also accepted.

Example 2

Input
n = 3, start = 5
Output
[5, 4, 6, 7, 3, 2, 0, 1]
Why
All eight 3-bit values appear once, each step flips one bit, and 1 (001) to 5 (101) also flips one bit.

Example 3

Input
n = 1, start = 0
Output
[0, 1]
Why
With one bit there are only two values, and they differ in that bit.

Constraints

  • 1 <= n <= 16
  • 0 <= start < 2^n
  • Any valid order is accepted.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (backtracking)O(n · 2^n) in practice, exponential in the worst caseO(2^n)
Optimal (Gray code XOR start)O(2^n)O(1) extra

1Brute force (backtracking)

TimeO(n · 2^n) in practice, exponential in the worst caseTrying low bits first happens to trace a Gray code with no dead ends, but a general backtracking search gives no such guarantee.
SpaceO(2^n)The visited array, the path and the recursion stack all hold up to 2^n entries.

Treat each value as a node joined to the n values that differ in one bit. Starting from start, walk to unvisited neighbours with depth-first search, undoing a step when it gets stuck. When all 2^n values are used, accept only if the last one is a neighbour of start.

  1. Mark start visited and put it in the path.
  2. dfs(cur): if the path holds all 2^n values, return whether cur ^ start has exactly one set bit.
  3. For each bit b, try next = cur ^ (1 << b) if unvisited: add it, recurse, and return true on success; otherwise remove it.
class Solution {
    private boolean[] seen;
    private List<Integer> path;
    private int n, start, total;

    public List<Integer> circularPermutation(int n, int start) {
        this.n = n;
        this.start = start;
        this.total = 1 << n;
        seen = new boolean[total];
        path = new ArrayList<>();
        seen[start] = true;
        path.add(start);
        dfs(start);
        return path;
    }

    private boolean dfs(int cur) {
        if (path.size() == total) {
            return Integer.bitCount(cur ^ start) == 1;
        }
        for (int b = 0; b < n; b++) {
            int next = cur ^ (1 << b);
            if (seen[next]) continue;
            seen[next] = true;
            path.add(next);
            if (dfs(next)) return true;
            path.remove(path.size() - 1);
            seen[next] = false;
        }
        return false;
    }
}

2Optimal (Gray code XOR start)

TimeO(2^n)One constant-time formula per output value.
SpaceO(1) extraNothing besides the output list.

The i-th reflected Gray code is i ^ (i >> 1); consecutive codes differ in one bit, and the last code 2^(n-1) differs from the first code 0 in one bit too. XOR-ing every code with start keeps every difference the same ((a ^ s) ^ (b ^ s) = a ^ b) and makes the first value 0 ^ start = start.

  1. For i from 0 to 2^n - 1, append start ^ i ^ (i >> 1).
  2. Return the list.
class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            res.add(start ^ i ^ (i >> 1));
        }
        return res;
    }
}

Edge cases to test

  • n = 1: the list has just two values
  • start = 0 and start = 2^n - 1
  • The last value must also differ from start in exactly one bit

Hints

Hint 1

Think of the values as corners of an n-dimensional cube; you need a tour of all corners that returns home.

Hint 2

The standard reflected Gray code is such a tour starting at 0. How do you move a valid tour so it starts at start instead?

Hint 3

XOR every Gray code value with start: XOR with a fixed number keeps one-bit differences one-bit.

FAQ

What is the best time complexity for Circular Permutation in Binary Representation?

Optimal (Gray code XOR start) runs in O(2^n) time and O(1) extra extra space. One constant-time formula per output value.

Which pattern does Circular Permutation in Binary Representation use?

It is a bit manipulation problem that uses the tricks to remember pattern. Other problems with the same pattern: Number of 1 Bits, Set the rightmost unset bit, XOR of 1 to n Numbers.

Is there a brute force solution for Circular Permutation in Binary Representation?

Yes. Brute force (backtracking) takes O(n · 2^n) in practice, exponential in the worst case time and O(2^n) space. Treat each value as a node joined to the n values that differ in one bit.

Which edge cases should I test for Circular Permutation in Binary Representation?

n = 1: the list has just two values; start = 0 and start = 2^n - 1; The last value must also differ from start in exactly one bit.