Problema
Em uma sequência de código Gray, cada valor difere do anterior em exatamente um bit. O código Gray padrão (binário refletido) de i é i XOR (i >> 1): para 2 bits a sequência é 0, 1, 3, 2, ou seja, 00, 01, 11, 10 em binário. Encoders rotativos usam esse código para que uma leitura feita entre duas posições nunca fique muito errada.
Implemente gray_code(n).
Entrada
n: o número de bits.
Saída
Retorne os 2^n valores do código Gray binário refletido, em ordem, como inteiros, começando em 0. Para n = 0, retorne [0].
Restrições
0 ≤ n ≤ 16
Exemplos
Entrada:
n = 2
Saída esperada:
expected = [0, 1, 3, 2]
Entrada:
long long n = 2;
Saída esperada:
std::vector<long long> expected = {0, 1, 3, 2};
Entrada:
long n = 2;
Saída esperada:
long[] expected = new long[] {0, 1, 3, 2};
Explicação
Em binário a sequência é 00, 01, 11, 10, então a resposta é [0, 1, 3, 2].
Entrada:
n = 3
Saída esperada:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Entrada:
long long n = 3;
Saída esperada:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Entrada:
long n = 3;
Saída esperada:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};
Explicação
Cada valor é i XOR (i >> 1) para i de 0 a 7: [0, 1, 3, 2, 6, 7, 5, 4].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Faça i variar de 0 a 2^n − 1.
Dica 2
Cada valor do código Gray sai de i e de i deslocado uma posição para a direita.
Dica 3
Para n = 0, o laço roda uma vez e dá [0].
Complexidade esperada
tempo O(2^n), espaço extra O(2^n)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.