Problema
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
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].
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.