Gray Code — Binary XOR Construction
Sanjeev SharmaAdvertisement
Problem
Return the Gray code sequence for n bits (adjacent numbers differ by exactly 1 bit).
Approach — Formula
gray(i) = i ^ (i >> 1). Each Gray code differs from the previous by exactly one bit.
Time: O(2^n) | Space: O(2^n)
Solutions
Python
class Solution:
def grayCode(self, n: int) -> list[int]:
return [i^(i>>1) for i in range(1<<n)]
C++
class Solution {
public:
vector<int> grayCode(int n){
vector<int> res;
for(int i=0;i<(1<<n);i++) res.push_back(i^(i>>1));
return res;
}
};
Complexity
- Time: O(2^n) | Space: O(2^n)
Advertisement
