Gray Code Algorithm
The reflected binary code (RBC), also known exactly as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit).Gray codes are widely used to prevent spurious output from electromechanical switches and to facilitate mistake correction in digital communications such as digital terrestrial television and some cable television systems.
class Solution {
public:
vector<int> grayCode(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> gray_code;
for (int i = 0; i < (1 << n); i++)
gray_code.push_back((i >> 1) ^ i);
return gray_code;
}
};
// More comprehensible solution
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result(1, 0);
for (int i = 0; i < n; i++) {
int curr = result.size();
while (curr) {
curr--;
int x = result[curr];
result.push_back((1 << i) + x);
}
}
return result;
}
};
