मध्यम 0 हल किए गए 0% स्वीकृति

Gray Code

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

आप क्या सीखेंगे

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

समस्या

अनुवाद दिखाएँ

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

सीमाएँ

0 ≤ n ≤ 16

उदाहरण

उदाहरण 1
इनपुट:
n = 2

अपेक्षित आउटपुट:
expected = [0, 1, 3, 2]
इनपुट:
long long n = 2;

अपेक्षित आउटपुट:
std::vector<long long> expected = {0, 1, 3, 2};
इनपुट:
long n = 2;

अपेक्षित आउटपुट:
long[] expected = new long[] {0, 1, 3, 2};

व्याख्या

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

उदाहरण 2
इनपुट:
n = 3

अपेक्षित आउटपुट:
expected = [0, 1, 3, 2, 6, 7, 5, 4]
इनपुट:
long long n = 3;

अपेक्षित आउटपुट:
std::vector<long long> expected = {0, 1, 3, 2, 6, 7, 5, 4};
इनपुट:
long n = 3;

अपेक्षित आउटपुट:
long[] expected = new long[] {0, 1, 3, 2, 6, 7, 5, 4};

व्याख्या

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

कैसे हल करें

पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।

संकेत 1

Loop i from 0 to 2^n − 1.

संकेत 2

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

संकेत 3

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

अपेक्षित जटिलता

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

संदर्भ

यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।