Разбор задачи 89. Gray Code с Литкода

https://leetcode.com/problems/gray-code/description/

Условие

Последовательность n-битного кода Грея — это последовательность из 2ⁿ целых чисел, в которой:

Каждое числое в диапазоне [0, 2n - 1] включительно
Первое число 0,
Каждое целое число встречается в последовательности не более одного раза,
Двоичное представление каждой пары соседних целых чисел отличается ровно на один бит, и
Двоичное представление первого и последнего целых чисел отличается ровно на один бит.

Дано число n, верните любую допустимую последовательность n-битного кода Грея.

Пример 1:

Ввод: n = 2
Вывод: [0,1,3,2]
Объяснение:
Двоичное представление of [0,1,3,2] is [00,01,11,10].
- 00 and 01 отличается на один бит
- 01 and 11 отличается на один бит
- 11 and 10 отличается на один бит
- 10 and 00 отличается на один бит
[0,2,3,1] также валидная последовательность кода Грея, двоичное представление которой [00,10,11,01].
- 00 and 10 отличается на один бит
- 10 and 11 отличается на один бит
- 11 and 01 отличается на один бит
- 01 and 00 отличается на один бит

Пример 2:

Ввод: n = 1
Вывод: [0,1]

Ограничения:

1 <= n <= 16

Решение

Если n = 3, то у нас числа от 0 до 111 в двоичном представлении.

Подготовим переменную для результата
var result = new List<int>();

Подготовим переменную для 2^n:
var max = (1 << n);

Подготовим массив для определения, использовано ли число ранее:
var used = new bool[max];

Индексы этого массива числа от 0 до max - 1, т.е. от 0 до 2^n - 1. Если по индексу, например, 5 стоит false, то это значит число 5 ещё не было в последовательности, если true, то было, и мы должны его пропустить. По умолчанию все значения false.

Положим в результат число 0, и сделаем отметку, что оно заюзано.

used[0] = true;
result.Add(0);

Далее мы будем идти по оставшимся числам:
for (var j = 1; j < max; j++)

Как нам найти следующее число?
Мы должны изменить один бит в последнем числе, после этого мы получим потенциально новое число. Мы должны проверить по массиву used, оно использовано ранее или нет. Если да, то его пропускаем и меняем другой бит.

Положим последнее число в переменную num (сначала это 0).
var num = 0;

Проходим по всем битам этого числа
for (var i = 0; i < n; i++)

Делаем маску из одного бита на месте i и всех нулей, т.е. 001b, 010b, 100b и т.д.
(1 << i)

Битово умножаем на эту маску последнее число:
var bit = num & (1 << i);

Если полученный результат больше 0, то значит на i'м месте у нас 1, и надо поменять его на 0.

Если результат 0, то значит на i'м месте у нас 0, и надо поменять его на 1.
с помощью xor c 1 мы можем поменять 1 на 0.
1 ^ 1 = 0

С помощью битового or, мы меняем 0 на 1:

0 | 1 = 1

Пока код получается таким:

var num = 0;//последнее число
for (var j = 1; j < max; j++)
{
    for (var i = 0; i < n; i++)
    {
    var bit = (num & (1 << i));
    var nextNumber = num;
    
    if (bit > 0)
    {
        nextNumber ^= 1 << i; 
    }
    else
    {
        nextNumber |= 1 << i;
    }
}

Теперь надо проверить заюзано ли число:
Если нет, то надо добавить его в результат, а в num положить последнее число.

if (!used[nextNumber])
{
    result.Add(nextNumber);//добавляем в результат
    used[nextNumber] = true;//число заюзано, больше его не повторять
    num = nextNumber;//новое последнее число
    break;//больше не меняем биты
}

Итого, код такой:

public class Solution {
    public IList<int> GrayCode(int n) {
        var result = new List<int>();
        var max = (1 << n);
        var used = new bool[max];
        used[0] = true;
        result.Add(0);
        var num = 0;
        for (var j = 1; j < max; j++)
        {
          for (var i = 0; i < n; i++)
          {
            var bit = (num & (1 << i));
            var nextNumber = num;
            
            if (bit > 0)
            {
                nextNumber ^= 1 << i; 
            }
            else
            {
                nextNumber |= 1 << i;
            }
            
            if (!used[nextNumber])
            {
                result.Add(nextNumber);
                used[nextNumber] = true;
                num = nextNumber;
                break;
            }
          }
        }
        return result;
    }
}

Да, есть короткое решение, если знаешь особенности кода Грея.

public class Solution {
    public IList<int> GrayCode(int n) 
    {
        int count = 1 << n; // 2^n
        var result = new int[count];
        
        for (int i = 0; i < count; i++) 
        {
            result[i] = i ^ (i >> 1);
        }
        
        return result;
    }
}

Но о нём вряд ли догадаешься сам, если не знаешь. Особенно на собесе.