Gray Code LeetCode Solution

Last updated on October 10th, 2024 at 12:09 am

Here, We see Gray Code LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Backtracking

Companies

Amazon

Level of Question

Medium

Gray Code LeetCode Solution

Gray Code LeetCode Solution

Problem Statement

An n-bit gray code sequence is a sequence of 2n integers where:

  • Every integer is in the inclusive range [0, 2n - 1],
  • The first integer is 0,
  • An integer appears no more than once in the sequence,
  • The binary representation of every pair of adjacent integers differs by exactly one bit, and
  • The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

1. Gray Code Leetcode Solution C++

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans(1<<n);
        for (int i=0; i<(1<<n); i++) 
            ans[i] = i^(i>>1);
        return ans;        
    }
};

2. Gray Code Leetcode Solution Java

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList();
        res.add(0);
        for(int i=1;i<=n;i++){
            int count = res.size()-1;
            int add = (int)Math.pow(2,i-1);
            while(count>=0)
                   res.add(add+res.get(count--));
            }
     return res;        
    }
}

3. Gray Code Leetcode Solution JavaScript

var grayCode = function(n) {
    const codeCount = 1 << n;
    let result = [];
    for(let i = 0 ; i < codeCount ; i++){
        code = i ^ ( i >> 1);
        result.push( code );
    }
    return result    
};

4. Gray Code Leetcode Solution Python

class Solution(object):
    def grayCode(self, n):
	res = [0]
	for i in range(1, 2**n):
		res.append(res[-1] ^ (i & -i))
	return res        
Scroll to Top