Gray to Binary Equivalent

Problem

Given an integer number n, which is a decimal representation of Gray Code, find the binary equivalent of the Gray Code and return the decimal representation of the binary equivalent.

Example

Example 1:

Input:
n = 4

Output:
7

Explanation:
Given 4, its gray code = 110.
Binary equivalent of the gray code 110 is 100.
Return 7 representing gray code 100.

Example 2:

Input:
n = 15

Output:
10
Explanation:

Given 15 representing gray code 1000.
Binary equivalent of gray code 1000 is 1111.
Return 10 representing gray code 1111 (binary 1010).

Your Task: You don't need to read input or print anything. Your task is to complete the function grayToBinary() which accepts an integer n as an input parameter and returns the decimal representation of the binary equivalent of the given gray code.

• Expected Time Complexity: $O(log (n))$.
• Expected Auxiliary Space: $O(1)$ .

Constraints:

• $0 <= n <= 10^9$

Solutions

• Brute Force
• Bit Manipulation
• Optimized

Brute Force

This approach uses brute force by first converting the decimal number to binary and then applying Gray Code logic to find the decimal representation of the binary equivalent.

Implementation

• Convert decimal to binary.
• Apply Gray Code logic to get binary equivalent.
• Convert binary back to decimal.

Live Editor

function GrayToBinaryBruteForce() {
  const decimalInput = 15; // Sample input

  const grayToBinaryBruteForce = function (n) {
    let binary = [];
    while (n) {
      binary.push(n % 2);
      n = Math.floor(n / 2);
    }
    while (binary.length < 32) {
      binary.push(0);
    }
    binary.reverse();

    let grayCode = [];
    let j = 0;
    while (binary[j] === 0) {
      j++;
    }
    grayCode[j] = binary[j];
    for (let i = j + 1; i < 32; i++) {
      grayCode[i] = grayCode[i - 1] ^ binary[i];
    }

    let grayCodeNum = 0;
    for (let i = 31; i >= 0; i--) {
      if (grayCode[i]) {
        grayCodeNum += Math.pow(2, 31 - i);
      }
    }

    return grayCodeNum;
  };

  const result = grayToBinaryBruteForce(decimalInput);

  return (
    <div>
      <p>
        <b>Input:</b> n = {decimalInput}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}

Result

Loading...

Code Snippets

JavaScript

class Solution {
decimalToBinary(binary, n) {
  while (n) {
      if (n % 2) binary.push(1);
      else binary.push(0);
      n = Math.floor(n / 2);
  }
  
  while (binary.length < 32) binary.push(0);
  
  binary.reverse();
}

help(binary) {
  const grayCode = new Array(32).fill(0);
  
  let j = 0;
  while (binary[j] === 0) j++;
  
  grayCode[j] = binary[j];
  for (let i = j + 1; i < 32; i++) {
      grayCode[i] = grayCode[i - 1] ^ binary[i];
  }
  
  let grayCodeNum = 0;
  for (let i = 31; i >= 0; i--) {
      if (grayCode[i]) grayCodeNum += 2 ** (31 - i);
  }
  
  return grayCodeNum;
}

grayToBinary(n) {
  const binary = [];
  this.decimalToBinary(binary, n);
  return this.help(binary);
}
}

TypeScript

class Solution {
decimalToBinary(binary: number[], n: number): void {
  while (n) {
      if (n % 2) binary.push(1);
      else binary.push(0);
      n = Math.floor(n / 2);
  }
  
  while (binary.length < 32) binary.push(0);
  
  binary.reverse();
}

help(binary: number[]): number {
  const grayCode: number[] = new Array(32).fill(0);
  
  let j = 0;
  while (binary[j] === 0) j++;
  
  grayCode[j] = binary[j];
  for (let i = j + 1; i < 32; i++) {
      grayCode[i] = grayCode[i - 1] ^ binary[i];
  }
  
  let grayCodeNum = 0;
  for (let i = 31; i >= 0; i--) {
      if (grayCode[i]) grayCodeNum += 2 ** (31 - i);
  }
  
  return grayCodeNum;
}

grayToBinary(n: number): number {
  const binary: number[] = [];
  this.decimalToBinary(binary, n);
  return this.help(binary);
}
}

C++

class Solution{
public:
void decimalToBinary(vector<int>& binary,int n)
{
  while(n)
  {
      if((n%2))
      binary.push_back(1);
      else
      binary.push_back(0);
      
      n/=2;
  }
  
  while(binary.size()<32)
  binary.push_back(0);
  
  reverse(binary.begin(),binary.end());
}
int help(vector<int>& binary)
{
  vector<int> grayCode(32,0);
  
  int j=0;
  while(binary[j]==0)
  j++;
  
  grayCode[j]=binary[j];
  for(int i=j+1;i<32;i++)
  grayCode[i]=grayCode[i-1]^binary[i];
  
  int grayCodeNum=0;
  for(int i=31;i>=0;i--)
  {
      if(grayCode[i])
      grayCodeNum+=pow(2,31-i);
  }
  return grayCodeNum;
}
int grayToBinary(int n)
{
  vector<int> binary;
  decimalToBinary(binary,n);
  return help(binary);
}
};

Python

class Solution:
def decimalToBinary(self, binary, n):
  while n:
      if n % 2:
          binary.append(1)
      else:
          binary.append(0)
      n //= 2
  
  while len(binary) < 32:
      binary.append(0)
  
  binary.reverse()

def help(self, binary):
  grayCode = [0] * 32
  
  j = 0
  while binary[j] == 0:
      j += 1
  
  grayCode[j] = binary[j]
  for i in range(j + 1, 32):
      grayCode[i] = grayCode[i - 1] ^ binary[i]
  
  grayCodeNum = 0
  for i in range(31, -1, -1):
      if grayCode[i]:
          grayCodeNum += 2 ** (31 - i)
  
  return grayCodeNum

def grayToBinary(self, n):
  binary = []
  self.decimalToBinary(binary, n)
  return self.help(binary)

Java

import java.util.*;

class Solution {
void decimalToBinary(ArrayList<Integer> binary, int n) {
  while (n > 0) {
      if (n % 2 == 1) binary.add(1);
      else binary.add(0);
      n /= 2;
  }
  
  while (binary.size() < 32) binary.add(0);
  
  Collections.reverse(binary);
}

int help(ArrayList<Integer> binary) {
  int[] grayCode = new int[32];
  
  int j = 0;
  while (binary.get(j) == 0) j++;
  
  grayCode[j] = binary.get(j);
  for (int i = j + 1; i < 32; i++) {
      grayCode[i] = grayCode[i - 1] ^ binary.get(i);
  }
  
  int grayCodeNum = 0;
  for (int i = 31; i >= 0; i--) {
      if (grayCode[i] == 1) grayCodeNum += Math.pow(2, 31 - i);
  }
  
  return grayCodeNum;
}

int grayToBinary(int n) {
  ArrayList<Integer> binary = new ArrayList<>();
  decimalToBinary(binary, n);
  return help(binary);
}
}

Complexity Analysis

• Time complexity: O(logN)
• Space complexity: O(32) (constant)

Note

To convert Gray code to binary efficiently, consider using bit manipulation techniques. Bitwise operations such as XOR (^) can be particularly useful in simplifying the conversion process, leading to optimized solutions with constant time complexity.

---

References

• LeetCode Problem: Best Time to Buy and Sell Stock
• Solution Link: Best Time to Buy and Sell Stock Solution on LeetCode
• Authors GeeksforGeeks Profile: Vipul lakum