Gray Code

Problem

The Gray code is a binary numeral system where two successive values differ in only one bit.

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

Every integer is in the inclusive range [0, 2^n - 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.

Examples

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]

Solution

Method 1 - Using Bitmask

Gray code sequences are designed such that consecutive integers differ by exactly one bit in their binary representation. One way to generate Gray code is to use the following algorithm:

Start with ( n = 1 ) and the sequence [0, 1].
For each additional bit, reflect the existing sequence and prefix the first half with ‘0’ and the second half with ‘1’.
Convert the binary representations back to integers.

Approach

Initialize the Sequence: Start with the sequence for ( n = 1 ), which is [0, 1].
Iterate and Extend the Sequence: For each bit from 2 to n, extend the current sequence by reflecting it and adding the necessary bit.
Convert Binary to Integer: Interpret the binary sequences as integers.

Code

Java

 class Solution {
     public List<Integer> grayCode(int n) {
         List<Integer> ans = new ArrayList<>();
         ans.add(0);
         for (int i = 0; i < n; i++) {
             int size = ans.size();
             for (int j = size - 1; j >= 0; j--) {
                 ans.add(ans.get(j) | (1 << i));
             }
         }
         return ans;
     }
 
     public static void main(String[] args) {
         Solution sol = new Solution();
         System.out.println(sol.grayCode(2)); // Output: [0, 1, 3, 2]
         System.out.println(sol.grayCode(1)); // Output: [0, 1]
     }
 }

Python

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0]
        for i in range(n):
            size = len(ans)
            for j in range(size - 1, -1, -1):
                ans.append(ans[j] | (1 << i))
        return ans

Complexity

⏰ Time complexity: O(2^n) because we generate ( 2^n ) integers.
🧺 Space complexity: O(2^n) because we store ( 2^n ) integers in the sequence.

Problem#

Examples#

Solution#

Method 1 - Using Bitmask#

Approach#

Code#

Java#

Python#

Complexity#