algoadvance

Leetcode 89. Gray Code

Problem Statement

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

Given an integer n representing the total number of bits in the code, return any sequence of Gray code. A Gray code sequence must begin with 0.

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
0 - 00
1 - 01
3 - 11
2 - 10
[0,1,3,2] is a Gray code sequence that meets the requirement for n = 2. Another valid sequence is [0,2,3,1].

Example 2:

Input: n = 1
Output: [0,1]

Constraints:

Clarifying Questions

  1. What is Gray code?
    • Gray code is a binary numeral system in which two successive values differ only in one bit.
  2. Do we need to generate all possible sequences of Gray code?
    • No, we only need to generate one valid sequence.
  3. What should the output format be?
    • The output should be a list of integers representing the Gray code sequence.

Strategy

  1. Understanding Gray Code Generation:
    • Gray code can be generated using a known algorithm that involves bit manipulation.
    • For a given integer i, its Gray code can be obtained by G(i) = i ^ (i >> 1), where ^ denotes the bitwise XOR operator, and >> denotes the right shift operator.
  2. Building the Sequence:
    • Initialize an empty list to store the Gray code sequence.
    • Loop through numbers from 0 to 2^n - 1, and for each number, apply the Gray code transformation i ^ (i >> 1).
    • Append the transformed result to the list.
  3. Returning the Sequence:
    • Return the constructed list as the result.

Code

import java.util.*;

public class GrayCode {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        int numberOfGrayCodes = 1 << n; // 2^n
        for (int i = 0; i < numberOfGrayCodes; i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }

    public static void main(String[] args) {
        GrayCode gc = new GrayCode();
        System.out.println(gc.grayCode(2));  // Output: [0, 1, 3, 2]
        System.out.println(gc.grayCode(1));  // Output: [0, 1]
    }
}

Time Complexity

By following this strategy and code, you can generate a valid sequence of Gray code for any integer n within the given constraints.

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