Médio 0 resolvidos 0% de aceitação

Código Gray

Liste o código Gray binário refletido de n bits, em que valores vizinhos diferem em exatamente um bit.

O que você vai aprender

  • Calcular um código Gray com XOR e deslocamento
  • Gerar 2^n valores
  • Verificar que vizinhos diferem em um bit

Problema

Ver original (inglês)

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

Exemplo 1
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].

Exemplo 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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.