Gray Code to Binary Conversion

Problem Statement

Given a gray code, write a program to convert the given gray code to binary code.

• Gray code- It has a property in which two successive numbers differ from each other by only one bit.
• Binary code- It is a default way of storing numbers. It is represented in form of zeros and ones.

Example

• Given gray code- 110101

• Output after converting gray code to binary code- 100110

Example Explanation

In this, the MSB or the Most Significant Bit of the gray code will always be equal to the MSB of the binary code which in this case is 1.

For changing the other bits of the gray code to binary code, check the gray code bit at that index. If the bit of the current index of gray code is zero then copy the previous bit of binary code else if it's one, then copy the inverted bit of the previous binary code.

Constraints

$0 <= N <= 10^8$

Approach 1: Binary to Gray Conversion

Algorithm:

• Initialize graycode as empty
• Add to the graycode, the first binary bit
• Iterate through for loop and add to the graycode, the Xor of binary code at the current index and binary code of previous index.
• return the graycode.

Program for Converting Binary Code to Gray in C++

Program to Convert Binary Code to Gray in Java

Program to Convert Binary Code to Gray using Python

Output:

Complexity Analysis

Since there is one for loop running inside the function, the time complexity is O(n) and the variable gray is used to for storing the output and hence the space complexity is also O(n).

Time Complexity: O(n)

Space Complexity: O(n)

Approach 2: Gray to Binary Conversion

• Initialize the binary string to empty
• To the binary string, append the first bit of the gray code
• Iterate using for loop from 1 to length of gray code
  • If the current bit of gray code is 0, then append the previous bit of binary code to the binary code.
  • Else flip the previous bit of the binary code and append it to the binary code.

Program to Convert Gray to Binary Code in C++

Program to Convert Gray to Binary in Java

Program to Convert Gray Code to Binary Code in Python

Output:

Complexity Analysis

Since there is one for loop running inside the function, the time complexity is O(n) and the variable gray is used for storing the output hence the space complexity is also O(n).

Time Complexity: O(n)

Space Complexity: O(n)

Approach 3: Binary to Gray Using Bitwise Operators

Algorithm:

• Initialize a function that takes binary numbers as the parameter.
• Perform that calculation, right shift the bit, and Xor it with the original number, i.e, $n ^ {(n >> 1)}$.
• Return the calculated number.

Program to Convert Binary to Gray Using the Bitwise Operator In C++

Program to Convert Binary to Gray Using the Bitwise Operator in Java

Program to Convert Binary to Gray Using the Bitwise Operator in Python

Output:

Complexity Analysis

Since there is no loop, the approach using bitwise operator is much faster and takes no space for storing the output.

Time Complexity: O(1)

Space Complexity: O(1)

Approach 4: Gray to Binary Using Bitwise Operators

Algorithm:

• Initialize the result as the number given by the user.
• Run a while loop till n > 0 and perform the following:
  • Right shift the number by 1
  • Xor the number with the result
• Return the result

Program To Convert Gray To Binary In C++

Program to Convert Gray to Binary in Java

Program to Convert Gray to Binary in Python

Output:

Complexity Analysis

Since there is just one loop and n is being right shifted in every iteration, the approach using bitwise operator is much faster and takes no space for storing the output.

Time Complexity: O(log(n))

Space Complexity: O(1)