Introduction-
This article will introduce Gray Code and provide approaches to use Gray Code in different data structure problems. Let’s first understand what exactly a Gray Code is?
Gray code is an ordering of the binary numeral system so that two successive values differ in only one bit.
Gray codes are used in a sequence of binary numbers generated by hardware that may cause an ambiguity during the no transition from one to next. Gray code comes to the rescue in these cases and can solve this problem quickly because only one bit changes its value during the transition from one number to another.
Example - Gray codes for 3-bit numbers are below:
| Binary | Gray |
| 000 | 000 |
| 001 | 001 |
| 010 | 011 |
| 011 | 010 |
| 100 | 110 |
| 101 | 111 |
| 110 | 101 |
| 111 | 100 |
Let’s Look at some problems related to Gray Code.
Find Gray Code
For the given number ‘N’, we have to find its gray code.
Let’s closely look at the bits of numbers and their gray code. We can notice that if the i-th bit of the number is 1 and the (i + 1)th bit is 0, then the i-th bit of gray code is 1.
If the i-th bit of the number is 0 and the (i + 1)th bit is 1, then the i-th bit of gray code is 1 as well.
Algorithm -
Step 1. Create a function that accepts an integer ‘N’.
Step 2. Shift ‘N’ rightwise by one and store it in the ‘temp’ variable.
Step 3. Do XOR of ‘N’ and ‘temp’.
Step 4. Return the result.
|
public class Solution {
public int getGrayCode(int n) {
// Shift rightwise by 1 int temp = n >> 1;
// Do XOR return n ^ temp; }
public static void main(String[] args) {
Solution solution = new Solution(); int result = solution.getGrayCode(4);
System.out.println(result);
}
} |
|
OUTPUT
6 |
Algorithm Complexity:
Time Complexity: O(1)
We are doing constant operations for finding gray code. Therefore, the overall time complexity will be O(1).
Space Complexity: O(1)
As no extra space is used, therefore overall space complexity will be O(1)
Read More - Time Complexity of Sorting Algorithms, and Euclid GCD Algorithm
Generate N-bit Gray Codes
We have been given the number ‘N’, and we have to return all the bit patterns from 0 to (2 ^ N) - 1 such that successive bits differ by 1.
For example: say N = 2, possible gray codes are below -
| Binary | Gray |
| 00 | 00 |
| 01 | 01 |
| 10 | 11 |
| 11 | 10 |
Approach 1
If we try to find patterns in these gray codes, we can see ‘N’ bit Gray Codes can be created from an (N - 1) bit list of Gray codes using the below algorithm steps.
Algorithm -
Step 1. Initialize list of String ‘res’.
Step 2. Add ‘0’ and ‘1’ in the ’res’.
Step 3. Make an iteration with the help of iterator pointer ‘i’ 2 to ‘2 ^ (N - 1)’ and execute steps 4 to 6 inside it.
Step 4. Make an iteration with the help of iterator pointer ‘j’ from ‘i - 1’ to 0 and copy all strings present at index ‘j’ in the ‘res’.
Step 5. Make another iteration with the help of iterator pointer ‘j’ from ‘0’ to ‘i - 1’ and append ‘0’ at beginning of strings present at index ‘j’.
Step 6. Make an iteration with the help of iterator pointer ‘j’ from ‘0’ to ‘2 * i’ and append ‘1’ at beginning of strings present at index ‘j’.
Step 7. Return ‘res’.
|
import java.util.ArrayList; import java.util.List;
public class Solution1 {
public List<String> generateGrayCodes(int n) { if (n <= 0) return null;
List<String> res = new ArrayList<String>();
res.add("0"); res.add("1");
// traverse from 0 to (2 ^ n) - 1 for (int i = 2; i < (1 << n); i = i << 1) { for (int j = i - 1 ; j >= 0 ; j--) { res.add(list.get(j)); }
// Adding 0 in beginning for (int j = 0 ; j < i ; j++) { res.set(j, "0" + list.get(j)); }
// Adding 1 in beginning for (int j = i ; j < 2 * i ; j++) { res.set(j, "1" + list.get(j)); } }
return res;
}
public static void main(String[] args) {
Solution1 solution = new Solution1();
List<String> list = solution.generateGrayCodes(3);
System.out.println(list);
}
} |
|
OUTPUT
2
|
Algorithm Complexity:
Time Complexity: O(2 ^ N)
As we are traversing for all the combinations of ‘N’, which will take exponential time complexity of O(2 ^ N) as we are making two choices for every element ’. Therefore the overall time complexity will be O(2 ^ N)
Space Complexity: O(2 ^ N)
As we have used auxiliary space for storing the gray 2 ^ N codes. Therefore the overall space complexity will be O(2 ^ N).
Approach 2 -
In the above approach, we are solving this problem iteratively. In this approach, let’s try to solve this problem recursively. We will keep on appending bits 0 and 1 every time till the time the no of bits is not equal to N.
Algorithm -
Step 1. Write a recursive function ‘generateGrayCodes()’ that accepts ‘N’ as the parameter.
Step 2. Base case will be for N = 0, return 0.
Step 3. Another base will be for N = 1, return 0 and 1.
Step 4. Call the recursive function for N - 1 and save the result in the ‘outputList’ list.
Step 5. Create a final list ‘res’ and merge both lists i.e, ‘outputList’ and ‘res’.
Step 6. Return list, ‘res’.
|
import java.util.ArrayList; import java.util.List;
public class Solution {
public List<String> generateGrayCodes(int n) { if (n <= 0) { List<String> res = new ArrayList<String>(); res.add("0"); return res; }
if(n == 1) { List<String> res = new ArrayList<String>(); res.add("0"); res.add("1"); return res; }
// Recursive call List<String> outputList = generateGrayCodes(n - 1);
ArrayList<String> res = new ArrayList<String>();
// Merging list by adding 0 in beginning for(int i = 0; i < outputList.size(); i++) { String temp = outputList.get(i); res.add("0" + temp);
}
// Merging list by adding 1 in beginning for(int i = outputList.size() - 1; i >= 0; i--) { String temp = outputList.get(i); res.add("1" + temp); }
return res; }
public static void main(String[] args) {
Solution solution = new Solution();
List<String> res = solution.generateGrayCodes(3);
System.out.println(res);
}
} |
As we are traversing for all the combinations of ‘N’ which is ‘2 ^ N’. Therefore overall time complexity will be O(2 ^ N).
Space Complexity: O(2 ^ N)
As we have used auxiliary space in our approach, which is storing 2 ^ N codes. Therefore the overall space complexity will be O(2 ^ N).
Approach 3 -
In this approach, we are using bitwise manipulation similar to the way we used to find gray code for a single number.
Algorithm -
Step 1. Write a function ‘generateGrayCodes()’ that accepts ‘N’ as the parameter.
Step 2. Iterate from 0 to (2 ^ N) - 1 and repeat steps 3 to 6.
Step 3. Do XOR of ‘N’ and N >> 1 and store the result in the variable named ‘ans’.
Step 4. Convert this result stored in ‘res’ from decimal to binary using ‘toBinaryString()’ function and store it in ‘temp’.
Step 5. Now print the ‘temp’
|
import java.util.LinkedList; import java.util.List;
public class Solution {
public void generateGrayCodes(int n) {
for (int i = 0; i < 1<<n; i++) { // Bitwise XOR int ans = i ^ (i >> 1);
// Convert decimal to binary String temp = Integer.toBinaryString(ans); System.out.println(temp); } }
public static void main(String[] args) {
Solution solution = new Solution();
solution.generateGrayCodes(3); }
} OUTPUT 2 |
Time Complexity: O(2^N)
As we are traversing for all the combinations of ‘N’ which is ‘2 ^ N’. Therefore overall time complexity will be O(2 ^ N).
Space Complexity: O(1)
As we are not using any extra space here therefore, the overall space complexity will be constant which means O(1).
Must read decimal to binary c++
Frequently asked questions-
1) What is a Gray Code?
Gray code is an ordering of the binary numeral system in such a way that two successive values differ in only one bit.
2) Where are Gray codes used?
Gray codes are used in the sequence of binary numbers generated by hardware that may cause an ambiguity during the no transition from one to next.
3) What is the Formula to calculate Gray Code?
The gray Code for number n can be calculated using the below formula -
(n) ^ (n >> 1) .
Key takeaways-
In this article, we discussed what Gray code is and what are the different ways possible to calculate it programmatically. We understand how we can leverage bitwise manipulation techniques to generate gray code for any number. If you want to practice more problems, then you can visit Coding Ninjas Studio.
Check out this problem - XOR Queries On Tree
If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.
Until then, All the best for your future endeavors, and Keep Coding.
By Harsh Goyal
24+ registered 
