Sponsored
Sponsored
Gray code can be generated using a simple bit manipulation technique. For a given integer k, the corresponding Gray code is obtained by XORing k with (k >> 1). This technique ensures that each step in changing numbers results in transitioning only one bit.
Time complexity: O(2n), traversing all numbers.
Space complexity: O(1), using constant extra space.
1using System;
2
3class GrayCode {
4 static void Main() {
5 int n = 2;
6 GrayCodeSequence(n);
7 }
8
9 static void GrayCodeSequence(int n) {
10 int size = 1 << n;
11 for (int i = 0; i < size; i++) {
12 int gray = i ^ (i >> 1);
13 Console.Write(gray + " ");
14 }
15 }
16}This C# program generates the Gray code sequence using the bit manipulation method i ^ (i >> 1) within a loop iterating over a 2n range.
The Gray code can be recursively generated by reflecting the existing sequence. Start with a base case of n=1: [0,1]. For each subsequent n, reflect the current list, prepend a bit to the reflected part, and concatenate the results: if Gn-1 = [0, 1], then Gn = [0Gn-1, 1Gn-1].
Time complexity: O(2n), where recursions reflect and build upon previous results.
Space complexity: O(2n), allocating for the result array.
1
This Python solution recursively computes Gray codes by reflecting the previously computed sequence and appending bit-changed reflections.