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

ग्रे कोड (Gray Code)

n-बिट reflected binary ग्रे कोड की सूची बनाइए, जिसमें पड़ोसी मान ठीक एक बिट में अलग होते हैं।

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

  • XOR और shift से ग्रे कोड निकालना
  • 2^n मान बनाना
  • जाँचना कि पड़ोसी मान एक बिट में अलग हैं

समस्या

ग्रे कोड के क्रम में हर मान अपने पिछले मान से ठीक एक बिट में अलग होता है। i का मानक (reflected binary) ग्रे कोड i XOR (i >> 1) है: 2 बिट्स के लिए क्रम 0, 1, 3, 2 है, जो binary में 00, 01, 11, 10 है। Rotary encoder में इसी का इस्तेमाल होता है, ताकि दो स्थितियों के बीच ली गई रीडिंग कभी बहुत ग़लत न हो।

gray_code(n) लिखिए।

इनपुट

n: बिट्स की संख्या।

आउटपुट

reflected binary ग्रे कोड के 2^n मान क्रम से, पूर्णांकों के रूप में, 0 से शुरू करके लौटाइए। n = 0 के लिए [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};

व्याख्या

binary में क्रम 00, 01, 11, 10 है, इसलिए उत्तर [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};

व्याख्या

i = 0 से 7 तक हर मान i XOR (i >> 1) है: [0, 1, 3, 2, 6, 7, 5, 4]।

कैसे हल करें

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

संकेत 1

i को 0 से 2^n − 1 तक loop कीजिए।

संकेत 2

हर ग्रे कोड मान i से और i को एक स्थान दाईं ओर shift करके मिली संख्या से बनता है।

संकेत 3

n = 0 के लिए loop एक बार चलता है और [0] देता है।

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

समय O(2^n), अतिरिक्त स्थान O(2^n)

संदर्भ

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

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

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

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

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

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