If you never heard of this, please read wiki first and ten check this post and you will understand the whole mechanism. But if you are quite eager to check the formula then check this directly.

Bang! End of story!

- space cost O(2^n)
- time cost O(n)

```
//AC - 0ms;
int grayCode(int n, int* returnSize)
{
*returnSize = 0;
int *arr = (int*)malloc(sizeof(int));
n = 1<<n;
for(int i = 0; i < n; i++)
{
*returnSize += 1;
arr = (int*)realloc(arr, sizeof(int)*(*returnSize));
arr[*returnSize-1] = i^(i>>1);
}
return arr;
}
```