Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.

Пример:

Input: n = 2, start = 3
Output: [3,2,0,1]

👨‍💻 Алгоритм:

1⃣Генерация Грей-кода:
Генерация Грей-кода для чисел от 0 до 2𝑛−1

2⃣Определение начальной позиции:
Находим индекс числа start в последовательности Грей-кода.

3⃣Построение перестановки:
Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.

😎 Решение:

import java.util.*;

public class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> gray = grayCode(n);
        int startIndex = gray.indexOf(start);
        List<Integer> result = new ArrayList<>();
        result.addAll(gray.subList(startIndex, gray.size()));
        result.addAll(gray.subList(0, startIndex));
        return result;
    }

    private List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        int numElements = 1 << n;
        for (int i = 0; i < numElements; i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний