89. Gray Code

1. 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.

2. Example

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]

3. Constraints

• 1 <= n <= 16

4. Solutions

Bit Manipulation

Time complexity: O($2^n$)
Space complexity: O(1)

// [000, 001, 011, 010, 110, 111, 101, 100] are first eight gray codes
// we can find that besides the first digit, later digits are repeat
// which means the i-th code has a rule between i and (i >> 1)
// & and | will get too many identical results, so we try ^ and it works
class Solution {
public:
    vector<int> grayCode(const int n) {
        vector<int> gray_codes(1 << n);
        for (int i = 0; i < gray_codes.size(); ++i) {
            gray_codes[i] = (i >> 1) ^ i;
        }

        return gray_codes;
    }
};