Задача: 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 и следуя по циклическому Грей-коду.

😎 Решение:

vector<int> grayCode(int n) {
    vector<int> result;
    int num_elements = 1 << n;
    for (int i = 0; i < num_elements; ++i) {
        result.push_back(i ^ (i >> 1));
    }
    return result;
}

vector<int> circularPermutation(int n, int start) {
    vector<int> gray = grayCode(n);
    auto start_iter = find(gray.begin(), gray.end(), start);
    vector<int> result;
    result.insert(result.end(), start_iter, gray.end());
    result.insert(result.end(), gray.begin(), start_iter);
    return result;
}

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