Algorithm
Problem Name: 89. 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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int* grayCode(int n, int* returnSize) {
int i, j;
int *p, psz, pn;
psz = 1 << n;
p = malloc(psz * sizeof(int));
//assert(p);
pn = 0;
p[pn ++] = 0;
for (i = 0; i < n; i ++) {
for (j = pn - 1; j >= 0; j --) {
p[pn ++] = p[j] | (1 << i);
}
}
*returnSize = pn;
return p;
}
Input
n = 2
Output
[0,1,3,2]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List grayCode(int n) {
if (n == 0) {
List ans = Arrays.asList(0);
return ans;
}
List < String> arr = new ArrayList<>();
// Base case for 1
arr.add("0");
arr.add("1");
int c = 1;
while(c < n) {
for (int i=0;i<arr.size();i++) {
arr.set(i, "0" + arr.get(i));
}
int rev = arr.size()-1;
while (rev >= 0) {
arr.add("1" + arr.get(rev).substring(1));
rev--;
}
c++;
}
List < Integer> ans = getDecimalList(arr);
return ans;
}
public List < Integer> getDecimalList(List arr) {
List ans = new ArrayList<>();
for (String s : arr) {
ans.add(Integer.parseInt(s, 2));
}
return ans;
}
}
Input
n = 2
Output
[0,1,3,2]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const grayCode = function(n) {
if (n === 0) {
return [0]
}
const temp = grayCode(n - 1)
const nums = [].concat(temp)
const addNum = 1 << (n - 1)
for (let i = temp.length - 1; i >= 0; i--) {
nums.push(addNum + temp[i])
}
return nums
}
Input
n = 1
Output
[0,1]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def grayCode(self, n: int) -> List[int]:
results = [0]
for i in range(n):
results += [x + pow(2, i) for x in reversed(results)]
return results
Input
n = 2
Output
[0,1,3,2]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _089_GrayCode
{
public IList < int> GrayCode(int n)
{
var result = new List<int>() { 0 };
if (n == 0) return result;
result.Add(1);
var pointer = 1;
while (pointer < n)
{
var value = 1 << pointer;
for (var i = result.Count - 1; i >= 0; i--)
{
result.Add(value + result[i]);
}
pointer++;
}
return result;
}
}
}
Input
n = 2
Output
[0,1,3,2]