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.
1def gray_code(n):
2 size = 1 << n
3 for i in range(size):
4 gray = i ^ (i >> 1)
5 print(gray, end=' ')
6
7n = 2
8gray_code(n)This Python script computes Gray codes for the range 0 to 2n - 1 using bit manipulation: i ^ (i >> 1). Each result is printed immediately.
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#include <vector>
std::vector<int> grayCode(int n) {
if (n == 0) return {0};
std::vector<int> lower = grayCode(n - 1);
std::vector<int> result = lower;
int size = lower.size();
for (int i = size - 1; i >= 0; i--) {
result.push_back(lower[i] | (1 << (n - 1)));
}
return result;
}
int main() {
int n = 2;
std::vector<int> gray = grayCode(n);
for (int code : gray) {
std::cout << code << " ";
}
return 0;
}C++ recursive implementation that builds Gray code by reflecting lower and appending prefixed values. The base case starts with least significant bit.