1238 Circular Permutation in Binary Representation Solution

The problem

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

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).

Python

def circularPermutation(n, start):
    size = 1 << n
    result = [(i ^ (i >> 1)) for i in range(size)]
    startIndex = result.index(start)
    return result[startIndex:] + result[:startIndex]

Java

import java.util.*;

public class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        int size = 1 << n;
        List<Integer> result = new ArrayList<>();
        int startIndex = 0;
        
        for (int i = 0; i < size; ++i) {
            int grayCode = i ^ (i >> 1);
            result.add(grayCode);
            if (grayCode == start) {
                startIndex = i;
            }
        }
        
        Collections.rotate(result, -startIndex);
        return result;
    }
}

C++

#include <vector>

std::vector<int> circularPermutation(int n, int start) {
    int size = 1 << n;
    std::vector<int> result(size);
    int startIndex = 0;
    
    for (int i = 0; i < size; ++i) {
        result[i] = i ^ (i >> 1);
        if (result[i] == start) {
            startIndex = i;
        }
    }
    
    std::vector<int> circularResult(size);
    for (int i = 0; i < size; ++i) {
        circularResult[i] = result[(startIndex + i) % size];
    }
    
    return circularResult;
}

JavaScript

function circularPermutation(n, start) {
    let size = 1 << n;
    let result = new Array(size);
    let startIndex = 0;
    
    for (let i = 0; i < size; ++i) {
        let grayCode = i ^ (i >> 1);
        result[i] = grayCode;
        if (grayCode === start) {
            startIndex = i;
        }
    }
    
    return [...result.slice(startIndex), ...result.slice(0, startIndex)];
}

#include <stdio.h>
#include <stdlib.h>

int* circularPermutation(int n, int start, int* returnSize) {
    int size = 1 << n;
    int* result = (int*)malloc(size * sizeof(int));
    int startIndex = 0;
    *returnSize = size;
    
    for (int i = 0; i < size; ++i) {
        result[i] = i ^ (i >> 1);
        if (result[i] == start) {
            startIndex = i;
        }
    }
    
    int* circularResult = (int*)malloc(size * sizeof(int));
    for (int i = 0; i < size; ++i) {
        circularResult[i] = result[(startIndex + i) % size];
    }
    
    free(result);
    return circularResult;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> CircularPermutation(int n, int start) {
        int size = 1 << n;
        List<int> result = new List<int>(size);
        int startIndex = 0;
        
        for (int i = 0; i < size; ++i) {
            int grayCode = i ^ (i >> 1);
            result.Add(grayCode);
            if (grayCode == start) {
                startIndex = i;
            }
        }
        
        List<int> circularResult = new List<int>(size);
        for (int i = 0; i < size; ++i) {
            circularResult.Add(result[(startIndex + i) % size]);
        }
        return circularResult;
    }
}

This Python solution uses list comprehension to generate the Gray codes and employs slicing to rotate the list to begin with start.

Complexity

Time Complexity: O(2^n)
Space Complexity: O(2^n)

Try this approach in the editor

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.

Python

def backtrack(result, curr, used, size, found):
    if found[0]:
        return
    if curr == size:
        found[0] = True
        return
    for i in range(size):
        if not used[i] and (curr == 0 or bin(result[curr - 1] ^ i).count('1') == 1):
            used[i] = True
            result[curr] = i
            backtrack(result, curr + 1, used, size, found)
            if found[0]:
                return
            used[i] = False


def circularPermutation(n, start):
    size = 1 << n
    result = [0] * size
    used = [False] * size
    found = [False]

    result[0] = start
    used[start] = True
    backtrack(result, 1, used, size, found)

    return result

Java

import java.util.*;

public class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        int size = 1 << n;
        List<Integer> result = new ArrayList<>(Collections.nCopies(size, 0));
        boolean[] used = new boolean[size];
        boolean[] found = new boolean[1];

        result.set(0, start);
        used[start] = true;
        backtrack(result, 1, used, size, found);
        return result;
    }

    private void backtrack(List<Integer> result, int curr, boolean[] used, int size, boolean[] found) {
        if (found[0]) return;
        if (curr == size) {
            found[0] = true;
            return;
        }
        for (int i = 0; i < size; ++i) {
            if (!used[i] && (curr == 0 || Integer.bitCount(result.get(curr - 1) ^ i) == 1)) {
                used[i] = true;
                result.set(curr, i);
                backtrack(result, curr + 1, used, size, found);
                if (found[0]) return;
                used[i] = false;
            }
        }
    }
}

C++

#include <vector>
#include <cmath>

void backtrack(std::vector<int>& result, int curr, std::vector<bool>& used, int size, bool& found) {
    if (found) return;
    if (curr == size) {
        found = true;
        return;
    }
    for (int i = 0; i < size; ++i) {
        if (!used[i] && (curr == 0 || __builtin_popcount(result[curr - 1] ^ i) == 1)) {
            used[i] = true;
            result[curr] = i;
            backtrack(result, curr + 1, used, size, found);
            if (found) return;
            used[i] = false;
        }
    }
}

std::vector<int> circularPermutation(int n, int start) {
    int size = 1 << n;
    std::vector<int> result(size);
    std::vector<bool> used(size, false);
    bool found = false;

    result[0] = start;
    used[start] = true;
    backtrack(result, 1, used, size, found);

    return result;
}

JavaScript

function circularPermutation(n, start) {
    const size = 1 << n;
    const result = Array(size).fill(0);
    const used = Array(size).fill(false);
    let found = [false];

    result[0] = start;
    used[start] = true;
    backtrack(result, 1, used, size, found);
    return result;

    function backtrack(result, curr, used, size, found) {
        if (found[0]) return;
        if (curr === size) {
            found[0] = true;
            return;
        }
        for (let i = 0; i < size; ++i) {
            if (!used[i] && (curr === 0 || countBits(result[curr - 1] ^ i) === 1)) {
                used[i] = true;
                result[curr] = i;
                backtrack(result, curr + 1, used, size, found);
                if (found[0]) return;
                used[i] = false;
            }
        }
    }

    function countBits(n) {
        let count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void backtrack(int* result, int curr, int mask, int* used, int size, int* found) {
    if (*found) return;
    if (curr == size) {
        *found = 1;
        return;
    }
    for (int i = 0; i < size; ++i) {
        if (!used[i] && (curr == 0 || __builtin_popcount(result[curr - 1] ^ i) == 1)) {
            used[i] = 1;
            result[curr] = i;
            backtrack(result, curr + 1, mask, used, size, found);
            if (*found) return;
            used[i] = 0;
        }
    }
}

int* circularPermutation(int n, int start, int* returnSize) {
    int size = 1 << n;
    int* result = (int*)malloc(size * sizeof(int));
    int* used = (int*)calloc(size, sizeof(int));
    int found = 0;
    *returnSize = size;

    result[0] = start;
    used[start] = 1;
    backtrack(result, 1, 0, used, size, &found);

    free(used);
    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> CircularPermutation(int n, int start) {
        int size = 1 << n;
        IList<int> result = new List<int>(new int[size]);
        bool[] used = new bool[size];
        bool[] found = new bool[1];

        result[0] = start;
        used[start] = true;
        Backtrack(result, 1, used, size, found);
        return result;
    }

    private void Backtrack(IList<int> result, int curr, bool[] used, int size, bool[] found) {
        if (found[0]) return;
        if (curr == size) {
            found[0] = true;
            return;
        }
        for (int i = 0; i < size; ++i) {
            if (!used[i] && (curr == 0 || CountBits(result[curr - 1] ^ i) == 1)) {
                used[i] = true;
                result[curr] = i;
                Backtrack(result, curr + 1, used, size, found);
                if (found[0]) return;
                used[i] = false;
            }
        }
    }

    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

The Python implementation uses recursion to attempt to build a valid permutation sequence, using a 'found' flag to stop recursion once a successful permutation is constructed.

Complexity

Time Complexity: O((2^n)!) in the worst case, limited by permutation rules.
Space Complexity: O(2^n)

Try this approach in the editor

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.

TypeScript

function circularPermutation(n: number, start: number): number[] {
    const ans: number[] = [];
    for (let i = 0; i < 1 << n; ++i) {
        ans.push(i ^ (i >> 1) ^ start);
    }
    return ans;
}

func circularPermutation(n int, start int) []int {
	g := make([]int, 1<<n)
	j := 0
	for i := range g {
		g[i] = i ^ (i >> 1)
		if g[i] == start {
			j = i
		}
	}
	return append(g[j:], g[:j]...)
}

Try this approach in the editor

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).

func circularPermutation(n int, start int) (ans []int) {
	for i := 0; i < 1<<n; i++ {
		ans = append(ans, i^(i>>1)^start)
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Gray Code Generation	Time Complexity: O(2^n) Space Complexity: O(2^n)
Backtracking with Validity Check	Time Complexity: O((2^n)!) in the worst case, limited by permutation rules. Space Complexity: O(2^n)
Binary Code to Gray Code	–
Conversion Optimization	–

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.

Frequently asked questions

Is Circular Permutation in Binary Representation easy or hard?

This problem is considered Medium difficulty. Generating permutations with adjacency constraints can be tricky, but recognizing the Gray code pattern simplifies the solution significantly and reduces the complexity to a straightforward O(2^n) construction.

Circular Permutation in Binary Representation Python or Java solution

Both Python and Java implementations follow the same Gray code logic: iterate from 0 to 2^n - 1, compute i ^ (i >> 1), then XOR with start. Append each value to a result list or array. The algorithm remains O(2^n) in both languages.

How to solve Circular Permutation in Binary Representation in O(2^n)?

Use Gray code generation. For each index i from 0 to 2^n - 1, compute the Gray code value using i ^ (i >> 1). Then XOR that value with the start number to shift the sequence so it begins at start while preserving the one-bit adjacency property.

What is the best approach for Circular Permutation in Binary Representation?

Gray Code generation is the most efficient and commonly expected solution. Generate the sequence using the formula g = i ^ (i >> 1) for all values from 0 to 2^n - 1, then XOR each element with the given start value. This preserves the one-bit difference between neighbors and guarantees a valid circular permutation in O(2^n) time.

Is Circular Permutation in Binary Representation asked at Google Amazon Meta?

This problem reflects concepts frequently used in interviews at companies like Google, Amazon, and Meta, especially topics involving bit manipulation, Gray codes, and graph traversal over bit states. Variants of Gray code generation and hypercube traversal appear in system and algorithm interviews.

What data structure is used in Circular Permutation in Binary Representation?

The optimal solution mainly relies on bit manipulation and arrays or lists to store the sequence. The backtracking approach additionally uses a hash set or boolean array to track visited numbers while exploring permutations.

What is the time complexity of Circular Permutation in Binary Representation?

The optimal Gray code solution runs in O(2^n) time because it generates exactly 2^n numbers using constant-time bit operations. Space complexity is also O(2^n) to store the resulting permutation.

Circular Permutation in Binary Representation solution and explanation

The problem

Approach overview

Approach 1: Gray Code Generation

Approach 2: Backtracking with Validity Check

Approach 3: Binary Code to Gray Code

Approach 4: Conversion Optimization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Circular Permutation in Binary Representation solution and explanation

The problem

Approach overview

Approach 1: Gray Code Generation

Approach 2: Backtracking with Validity Check

Approach 3: Binary Code to Gray Code

Approach 4: Conversion Optimization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems