LeetCode Problem 1238

Difficulty: 🟡 Medium
Topics: Math, Backtracking, Bit Manipulation

Solution

LeetCode 1238 - Circular Permutation in Binary Representation

Problem Understanding

This problem asks us to construct a special ordering of all integers from 0 to 2^n - 1. The ordering must satisfy the properties of a circular Gray code sequence.

We are given two integers:

• n, which determines how many numbers exist in the permutation
• start, which specifies the first number in the sequence

Since there are 2^n possible binary values using exactly n bits, the final permutation must contain every integer in the range [0, 2^n - 1] exactly once.

The important condition is that every adjacent pair of numbers must differ by exactly one bit in binary representation. This includes the final pair formed by the last and first elements, because the sequence is circular.

For example, if two numbers are:

• 0101
• 0111

they differ in exactly one bit position, so this transition is valid.

However:

• 0101
• 0011

differ in two bit positions, so this transition is invalid.

The constraints are relatively small:

• 1 <= n <= 16
• Maximum sequence size is 2^16 = 65536

This immediately suggests that generating the entire sequence is feasible in both time and memory. However, brute force permutation generation would still be impossible because 65536! is astronomically large.

The problem guarantees that a valid answer always exists. That is important because we do not need to handle impossible cases.

Several edge cases are worth considering:

• n = 1, where the sequence only contains two numbers
• start = 0, which corresponds directly to the standard Gray code ordering
• Large values of n, where efficiency matters
• Ensuring the sequence is circular, meaning the last and first elements also differ by one bit

The key challenge is constructing the sequence efficiently while preserving the one-bit difference property.

Approaches

Brute Force Approach

A brute force solution would attempt to generate all permutations of the numbers from 0 to 2^n - 1, then test whether each adjacent pair differs by exactly one bit.

To check whether two numbers differ by one bit, we can compute:

x ^ y

If the result contains exactly one set bit, then the numbers differ by one bit.

Although this approach is conceptually simple, it is completely impractical. Even for n = 4, there are 16! permutations, which is already enormous. For n = 16, brute force is impossible.

The brute force method does guarantee correctness because it exhaustively searches all possible permutations, but the runtime grows factorially.

Optimal Approach

The key observation is that the problem is fundamentally asking for a Gray code sequence.

A Gray code is an ordering of numbers where adjacent values differ by exactly one bit. Even better, the standard binary reflected Gray code is already circular, meaning the first and last elements also differ by one bit.

The standard Gray code formula is:

$G(i)=i\oplus(i\gg1)$

This formula generates the i-th Gray code value.

For example, with n = 2:

i	Binary i	Gray Code
0	00	00
1	01	01
2	10	11
3	11	10

Resulting sequence:

0, 1, 3, 2

Each adjacent pair differs by one bit, including the transition from 2 back to 0.

The remaining challenge is that the sequence must begin with start.

A beautiful property of Gray codes solves this immediately:

If we XOR every element in a Gray code sequence with the same value, adjacency relationships remain unchanged.

Therefore, we can simply generate the standard Gray code sequence and XOR every value with start.

This rotates the sequence logically so that:

0 XOR start = start

Thus, the sequence automatically begins with start.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((2^n)!)	O(2^n)	Tries all permutations and validates adjacency
Optimal	O(2^n)	O(2^n)	Uses Gray code generation and XOR transformation

Algorithm Walkthrough

1. Compute the total number of values in the sequence.

Since there are n bits, the total number of distinct integers is:

$2^n$

We store this as:

total = 1 << n

2. Generate the standard Gray code sequence.

For every integer i from 0 to 2^n - 1, compute:

gray = i ^ (i >> 1)

This produces the canonical Gray code ordering. 3. Shift the sequence so it starts with start.

We XOR every Gray code value with start:

value = gray ^ start

Because XOR preserves bit differences, the adjacency property remains valid. 4. Append each transformed value into the result list.

Since Gray code generation already visits every number exactly once, the transformed sequence also forms a valid permutation. 5. Return the final sequence.

Why it works

The standard Gray code sequence guarantees that every adjacent pair differs by exactly one bit, including the first and last elements.

XOR with a fixed value preserves Hamming distance. If two numbers differ by one bit before XOR, they still differ by one bit afterward.

Therefore, transforming every Gray code value with XOR preserves the circular adjacency property while ensuring the first element becomes start.

Python Solution

from typing import List

class Solution:

    def circularPermutation(self, n: int, start: int) -> List[int]:
        total_numbers = 1 << n
        result = []

        for i in range(total_numbers):
            gray_code = i ^ (i >> 1)
            result.append(gray_code ^ start)

        return result

The implementation begins by computing the total number of values in the sequence using bit shifting. Since 2^n equals 1 << n, this is both efficient and idiomatic.

The loop iterates through every index from 0 to 2^n - 1. For each index, the standard Gray code formula generates a value that differs by one bit from the previous Gray code.

The sequence is then transformed using XOR with start. This ensures the first element becomes start because:

0 ^ start == start

The transformed values are appended into the result list and returned.

The implementation is compact because the Gray code properties handle all adjacency requirements automatically.

Go Solution

func circularPermutation(n int, start int) []int {
    totalNumbers := 1 << n
    result := make([]int, 0, totalNumbers)

    for i := 0; i < totalNumbers; i++ {
        grayCode := i ^ (i >> 1)
        result = append(result, grayCode^start)
    }

    return result
}

The Go implementation follows the exact same logic as the Python version.

The result slice is initialized with capacity totalNumbers to avoid repeated reallocations during appends. Go integers are sufficient for the given constraints because the largest value is 2^16 - 1, which easily fits within a standard int.

Unlike Python, Go requires explicit slice allocation and does not support dynamic list growth as transparently, so preallocating capacity is a useful optimization.

Worked Examples

Example 1

Input:

n = 2
start = 3

Total numbers:

2^2 = 4

i	Binary i	Gray Code Formula	Gray Code	XOR with start=3	Result
0	00	0 ^ 0	00	00 ^ 11	11 = 3
1	01	1 ^ 0	01	01 ^ 11	10 = 2
2	10	2 ^ 1	11	11 ^ 11	00 = 0
3	11	3 ^ 1	10	10 ^ 11	01 = 1

Final sequence:

[3, 2, 0, 1]

Check adjacency:

Pair	Binary Forms	One Bit Difference
3 -> 2	11 -> 10	Yes
2 -> 0	10 -> 00	Yes
0 -> 1	00 -> 01	Yes
1 -> 3	01 -> 11	Yes

Example 2

Input:

n = 3
start = 2

Total numbers:

2^3 = 8

i	Gray Code	XOR with 2	Result
0	0	0 ^ 2	2
1	1	1 ^ 2	3
2	3	3 ^ 2	1
3	2	2 ^ 2	0
4	6	6 ^ 2	4
5	7	7 ^ 2	5
6	5	5 ^ 2	7
7	4	4 ^ 2	6

One valid output:

[2, 3, 1, 0, 4, 5, 7, 6]

Every adjacent pair differs by exactly one bit, including the circular transition from 6 back to 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(2^n)	We generate each number exactly once
Space	O(2^n)	The output sequence contains 2^n integers

The algorithm performs a constant amount of work for every number in the sequence. Since the sequence size itself is 2^n, both time and space complexity are linear in the output size.

No additional expensive data structures are required.

Test Cases

from typing import List

def differs_by_one_bit(a: int, b: int) -> bool:
    x = a ^ b
    return x != 0 and (x & (x - 1)) == 0

def validate(n: int, start: int, result: List[int]) -> bool:
    if result[0] != start:
        return False

    if len(result) != (1 << n):
        return False

    if len(set(result)) != (1 << n):
        return False

    for i in range(len(result)):
        nxt = result[(i + 1) % len(result)]

        if not differs_by_one_bit(result[i], nxt):
            return False

    return True

solution = Solution()

# Example 1
result = solution.circularPermutation(2, 3)
assert validate(2, 3, result)  # Basic 2-bit example

# Example 2
result = solution.circularPermutation(3, 2)
assert validate(3, 2, result)  # Standard 3-bit example

# Smallest possible n
result = solution.circularPermutation(1, 0)
assert validate(1, 0, result)  # Minimum size sequence

# Smallest n with different start
result = solution.circularPermutation(1, 1)
assert validate(1, 1, result)  # Start is maximum value

# Larger input
result = solution.circularPermutation(4, 7)
assert validate(4, 7, result)  # Medium-sized sequence

# Maximum start value
result = solution.circularPermutation(3, 7)
assert validate(3, 7, result)  # Largest possible start for n=3

# Zero start
result = solution.circularPermutation(5, 0)
assert validate(5, 0, result)  # Standard Gray code ordering

# Stress-style test
result = solution.circularPermutation(10, 512)
assert validate(10, 512, result)  # Large sequence

Test Summary

Test	Why
n=2, start=3	Verifies the first provided example
n=3, start=2	Verifies the second provided example
n=1, start=0	Tests minimum possible sequence size
n=1, start=1	Tests smallest input with nonzero start
n=4, start=7	Tests normal medium-sized input
n=3, start=7	Tests maximum possible start value
n=5, start=0	Tests standard Gray code sequence
n=10, start=512	Stress test for larger input size

Edge Cases

One important edge case is when n = 1. In this situation, only two numbers exist: 0 and 1. The sequence must still be circular, meaning both transitions must differ by one bit. A buggy implementation might mishandle the circular requirement, but the Gray code construction naturally produces [0, 1], which satisfies the condition.

Another important edge case is when start = 0. In this case, the XOR transformation has no effect, so the output becomes the standard Gray code sequence. Some implementations attempt to rotate the sequence manually, which can introduce indexing mistakes. The XOR-based approach avoids this complexity entirely.

A third important edge case is when start equals the maximum possible value, such as 2^n - 1. Large binary values with many set bits can expose mistakes in bit manipulation logic. Since XOR is mathematically consistent regardless of the number of set bits, the implementation handles these cases correctly without any special handling.

Finally, large values of n, especially n = 16, are important performance edge cases. Recursive backtracking solutions may become slow or consume excessive memory. The Gray code formula generates each value in constant time, so the implementation scales efficiently even at the upper constraint boundary.