Mittel 0 gelöst 0% Erfolgsquote

Gray Code

List the n-bit reflected binary Gray code, where neighbors differ in exactly one bit.

Das lernst du

  • Compute a Gray code with XOR and shift
  • Generate 2^n values
  • Check that neighbors differ in one bit

Problem

Übersetzung anzeigen

In a Gray code sequence each value differs from the previous one in exactly one bit. The standard (reflected binary) Gray code of i is i XOR (i >> 1): for 2 bits the sequence is 0, 1, 3, 2, which is 00, 01, 11, 10 in binary. Rotary encoders use it so that a reading taken between two positions is never wildly wrong.

Implement gray_code(n).

Input

n: The number of bits.

Output

Return the 2^n values of the reflected binary Gray code in order, as integers, starting with 0. For n = 0 return [0].

Einschränkungen

0 ≤ n ≤ 16

Beispiele

Beispiel 1
Eingabe:
n = 2

Erwartete Ausgabe:
expected = [0, 1, 3, 2]
Eingabe:
long long n = 2;

Erwartete Ausgabe:
std::vector<long long> expected = {0, 1, 3, 2};
Eingabe:
long n = 2;

Erwartete Ausgabe:
long[] expected = new long[] {0, 1, 3, 2};

Erläuterung

In binary the sequence is 00, 01, 11, 10, so the answer is [0, 1, 3, 2].

Beispiel 2
Eingabe:
n = 3

Erwartete Ausgabe:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
Eingabe:
long long n = 3;

Erwartete Ausgabe:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
Eingabe:
long n = 3;

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

Erläuterung

Each value is i XOR (i >> 1) for i = 0 to 7: [0, 1, 3, 2, 6, 7, 5, 4].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Loop i from 0 to 2^n − 1.

Hinweis 2

Each Gray code value comes from i and i shifted right by one.

Hinweis 3

For n = 0 the loop runs once and gives [0].

Erwartete Komplexität

O(2^n) time, O(2^n) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.