समस्या
ग्रे कोड के क्रम में हर मान अपने पिछले मान से ठीक एक बिट में अलग होता है। 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
उदाहरण
इनपुट:
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] है।
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।