89. Gray Code LeetCode Solution

In this guide, you will get 89. Gray Code LeetCode Solution with the best time and space complexity. The solution to Gray Code problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Gray Code solution in C++
Gray Code solution in Java
Gray Code solution in Python
Additional Resources

Problem Statement of Gray Code

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]

Constraints:

1 <= n <= 16

Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(2^n)

89. Gray Code LeetCode Solution in C++

class Solution {
 public:
  vector<int> grayCode(int n) {
    vector<int> ans{0};

    for (int i = 0; i < n; ++i)
      for (int j = ans.size() - 1; j >= 0; --j)
        ans.push_back(ans[j] | 1 << i);

    return ans;
  }
};
/* code provided by PROGIEZ */

89. Gray Code LeetCode Solution in Java

class Solution {
  public List<Integer> grayCode(int n) {
    List<Integer> ans = new ArrayList<>();
    ans.add(0);

    for (int i = 0; i < n; ++i)
      for (int j = ans.size() - 1; j >= 0; --j)
        ans.add(ans.get(j) | 1 << i);

    return ans;
  }
}
// code provided by PROGIEZ

89. Gray Code LeetCode Solution in Python

class Solution:
  def grayCode(self, n: int) -> list[int]:
    ans = [0]

    for i in range(n):
      for j in reversed(range(len(ans))):
        ans.append(ans[j] | 1 << i)

    return ans
 # code by PROGIEZ