Gray Code

Harsh Goyal
Last Updated: May 13, 2022

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 
000000
001001
010011
011010
100110
101111
110101
111100

 

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)

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 
0000
0101
1011
1110

 

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).

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 codestudio.

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

Was this article helpful ?
1 upvote