algoadvance

Leetcode 89. Gray Code

Problem Statement

The problem is to generate a sequence of Gray codes for a given number n.

Gray code is a binary numeral system where two successive values differ in only one bit.

For a given integer n, generate the sequence of 2^n Gray codes. A Gray code sequence must begin with 0.

Example:

For n = 2, the Gray code sequence is [0, 1, 3, 2]. Note that:

Clarifying Questions:

  1. Should the output Gray codes be in binary format or in decimal format?
    • The output should be in decimal format as shown in the example.
  2. Is there any specific order in which the Gray code sequence should be returned?
    • Yes, the sequence should start with 0 and any two successive values in the sequence should differ by exactly one bit.

Strategy

To generate Gray codes for a given integer n, we can use the following approach:

  1. Use the bit manipulation method to convert binary numbers to Gray code numbers.
  2. For an integer i (where 0 <= i < 2^n), the i-th Gray code can be obtained by using the formula: 
    gray(i) = i ^ (i >> 1)

    Here, ^ denotes the bitwise XOR operator, and >> denotes right shift.

Code

Let’s implement the solution in C++:

#include <vector>

class Solution {
public:
    std::vector<int> grayCode(int n) {
        std::vector<int> result;
        int totalNumbers = 1 << n; // 2^n
        for (int i = 0; i < totalNumbers; ++i) {
            result.push_back(i ^ (i >> 1));
        }
        return result;
    }
};

Explanation of Code

  1. Initialization: We declare a vector result to store the Gray codes.
  2. Total Numbers: The total number of Gray codes for n bits is 2^n, which is computed using 1 << n.
  3. Generating Gray Codes:
    • For each integer i from 0 to 2^n - 1, compute the Gray code using the formula i ^ (i >> 1).
    • Append the resulting Gray code to the result vector.
  4. Return Result: Finally, return the result vector containing the Gray codes.

Time Complexity

The time complexity of this approach is O(2^n). This is because we generate 2^n Gray codes, and each operation inside the loop (bitwise XOR and right shift) takes constant time, O(1). Hence, the overall time complexity is O(2^n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI