Intermedio 0 resueltos 0% de aceptación

Código Gray

Genera el código Gray binario reflejado de n bits, en el que valores vecinos difieren en exactamente un bit.

Lo que aprenderás

  • Calcular un código Gray con XOR y un desplazamiento
  • Generar 2^n valores
  • Comprobar que los vecinos difieren en un solo bit

Problema

Ver original (inglés)

En una secuencia de código Gray, cada valor difiere del anterior en exactamente un bit. El código Gray estándar (binario reflejado) de i es i XOR (i >> 1): con 2 bits la secuencia es 0, 1, 3, 2, que en binario es 00, 01, 11, 10. Los codificadores rotatorios lo usan para que una lectura tomada entre dos posiciones nunca se aleje demasiado del valor real.

Implementa gray_code(n).

Entrada

n: la cantidad de bits.

Salida

Devuelve los 2^n valores del código Gray binario reflejado, en orden, como enteros y empezando por 0. Para n = 0 devuelve [0].

Restricciones

0 ≤ n ≤ 16

Ejemplos

Ejemplo 1
Entrada:
n = 2

Salida esperada:
expected = [0, 1, 3, 2]
Entrada:
long long n = 2;

Salida esperada:
std::vector<long long> expected = {0, 1, 3, 2};
Entrada:
long n = 2;

Salida esperada:
long[] expected = new long[] {0, 1, 3, 2};

Explicación

En binario la secuencia es 00, 01, 11, 10, así que la respuesta es [0, 1, 3, 2].

Ejemplo 2
Entrada:
n = 3

Salida esperada:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Entrada:
long long n = 3;

Salida esperada:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Entrada:
long n = 3;

Salida esperada:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};

Explicación

Cada valor es i XOR (i >> 1) para i = 0 a 7: [0, 1, 3, 2, 6, 7, 5, 4].

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Recorre i desde 0 hasta 2^n − 1.

Pista 2

Cada valor del código Gray se obtiene a partir de i y de i desplazado una posición a la derecha.

Pista 3

Para n = 0 el bucle se ejecuta una vez y da [0].

Complejidad esperada

tiempo O(2^n), espacio extra O(2^n)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.