Description:
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.
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 in Python:
Python
from typing import List
class Solution:
def grayCode(self, n: int) -> List[int]:
# Initialize the result with the first code, which is always 0
result = [0]
# For each bit position from 0 to n-1
for i in range(n):
# Determine the size of the current result list
current_length = len(result)
# Iterate over the current list in reverse order
for j in range(current_length - 1, -1, -1):
# Append the new code formed by adding 1 at the ith bit position
result.append(result[j] | (1 << i))
return resultExplanation:
- Initialization:
- We start with the list
resultcontaining the first element0.
- We start with the list
- Bitwise Construction:
- We iterate through each bit position from
0ton-1. - For each bit position
i, we first determine the current length of theresultlist. - We then iterate over the
resultlist in reverse order. This is done to ensure that we can mirror the list and generate new Gray codes by setting thei-th bit. - For each element
result[j]in the current list, we create a new code by setting thei-th bit. This is done using the bitwise OR operationresult[j] | (1 << i)and append the new code to theresultlist.
- We iterate through each bit position from
- Return the result:
- After completing the iterations for all bit positions, the
resultlist contains the Gray code sequence.
- After completing the iterations for all bit positions, the
Key Points
- The Gray code sequence is generated by reflecting and mirroring the existing sequence while toggling the relevant bit.
- The bitwise operations ensure that only one bit is changed between successive numbers in the sequence.
- The approach efficiently constructs the sequence in O(2n) time, suitable for the given constraint 1≤n≤16.
This solution generates a valid Gray code sequence for a given integer n following the properties of the Gray code.
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function(n) {
// Initialize the result with the first code, which is always 0
let result = [0];
// For each bit position from 0 to n-1
for (let i = 0; i < n; i++) {
// Determine the size of the current result list
let currentLength = result.length;
// Iterate over the current list in reverse order
for (let j = currentLength - 1; j >= 0; j--) {
// Append the new code formed by adding 1 at the ith bit position
result.push(result[j] | (1 << i));
}
}
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> grayCode(int n) {
// Initialize the result list with the first code, which is always 0
List<Integer> result = new ArrayList<>();
result.add(0);
// For each bit position from 0 to n-1
for (int i = 0; i < n; i++) {
// Determine the size of the current result list
int currentLength = result.size();
// Iterate over the current list in reverse order
for (int j = currentLength - 1; j >= 0; j--) {
// Append the new code formed by adding 1 at the ith bit position
result.add(result.get(j) | (1 << i));
}
}
return result;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<int> GrayCode(int n) {
// Initialize the result list with the first code, which is always 0
List<int> result = new List<int>();
result.Add(0);
// For each bit position from 0 to n-1
for (int i = 0; i < n; i++) {
// Determine the size of the current result list
int currentLength = result.Count;
// Iterate over the current list in reverse order
for (int j = currentLength - 1; j >= 0; j--) {
// Append the new code formed by adding 1 at the ith bit position
result.Add(result[j] | (1 << i));
}
}
return result;
}
}