Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction-  
2.
Find Gray Code
3.
Algorithm -
3.1.
Algorithm Complexity: 
3.2.
Time Complexity: O(1)
3.3.
Space Complexity: O(1) 
Generate N-bit Gray Codes
1.
Approach 1
2.
Algorithm -
2.1.
Algorithm Complexity: 
2.2.
Time Complexity: O(2 ^ N)
2.3.
Space Complexity: O(2 ^ N) 
3.
Approach 2 -
3.1.
Algorithm -
3.2.
Space Complexity: O(2 ^ N) 
4.
Approach 3 -
4.1.
Algorithm -
4.2.
 
4.3.
Time Complexity: O(2^N)
4.4.
Space Complexity: O(1) 
5.
Frequently asked questions-
6.
Key takeaways-
Last Updated: Mar 27, 2024

Gray Code

Author Harsh Goyal
1 upvote

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp
Previous article
Count Number of Set Bits in an Integer
Next article
Number of Steps to Reduce a Number in Binary Representation to One
Live masterclass