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.
1public class GrayCode {
2 public static void main(String[] args) {
3 int n = 2;
4 grayCode(n);
5 }
6
7 public static void grayCode(int n) {
8 int size = (int) Math.pow(2, n);
9 for (int i = 0; i < size; i++) {
10 int gray = i ^ (i >> 1);
11 System.out.print(gray + " ");
12 }
13 }
14}This Java program uses bit manipulation to print Gray code series by iterating from 0 to 2n - 1, calculating each Gray code value using the expression i ^ (i >> 1).
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.
1using System.Collections.Generic;
class Program {
static List<int> GrayCode(int n) {
if (n == 0) return new List<int> { 0 };
List<int> lower = GrayCode(n - 1);
List<int> result = new List<int>(lower);
int addOn = 1 << (n - 1);
for (int i = lower.Count - 1; i >= 0; i--) {
result.Add(lower[i] | addOn);
}
return result;
}
static void Main() {
int n = 2;
List<int> gray = GrayCode(n);
Console.WriteLine(string.Join(" ", gray));
}
}This C# program recursively generates Gray code by first getting a baseline sequence, reflecting it and adjusting with bitwise operations, storing each new sequence state.