Сложность: 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 и следуя по циклическому Грей-коду.
😎 Решение:
def grayCode(n):
return [i ^ (i >> 1) for i in range(1 << n)]
def circularPermutation(n, start):
gray = grayCode(n)
start_index = gray.index(start)
return gray[start_index:] + gray[:start_index]
Ставь 👍 и забирай 📚 Базу знаний