Last updated on January 19th, 2025 at 05:57 pm

Here, we see a Gray Code LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking

Companies

Amazon

Level of Question

Medium

Gray Code LeetCode Solution

1. 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]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Bitwise XOR. This is because the Gray Code generation relies on the property of XOR to compute the next Gray Code value by performing a bitwise XOR operation between the current number and its right-shifted version (i ^ (i >> 1)).

3. Code Implementation in Different Languages

3.1 Gray Code 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;        
    }
};

3.2 Gray Code 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.3 Gray Code 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    
};

3.4 Gray Code 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        

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(2n)	O(2n)
Java	O(2n)	O(2n)
JavaScript	O(2n)	O(2n)
Python	O(2n)	O(2n)

• The code uses the Bitwise XOR pattern to generate Gray Codes efficiently.
• The time and space complexity for all implementations are O(2ⁿ), as the number of Gray Codes grows exponentially with the number of bits n.
• The implementations are optimized for their respective languages, but the underlying logic remains the same.