algoadvance

The problem is to generate a sequence called Gray Code for a given number of bits n. Gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, we need to return any sequence of Gray code.

Example:

Input: n = 2
Output: [0, 1, 3, 2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

Given n = 2, [0, 1, 3, 2] is a valid Gray code sequence. Another valid sequence is [0, 2, 3, 1].

Clarifying Questions

  1. Does the order of the Gray code sequence matter?
    • The sequence must follow the rule that successive values differ by exactly one bit, but otherwise any valid sequence is acceptable.
  2. What should be the return type?
    • The function should return a list of integers representing the Gray code sequence.
  3. What about edge cases like n = 0?
    • For n = 0, the Gray code sequence would be [0].

Once these clarifications are made, we can proceed with solving the problem.

Strategy

  1. Initialization (Base Case):
    • Start with the simplest Gray code sequence, which is [0] for n = 0.
  2. Generate Sequence Iteratively:
    • For every new bit level from 1 to n, build the new sequence based on the existing sequence.
  3. Reflect and Append:
    • Reflect the current sequence (reverse it), and for each reflected value, add a 1 at the beginning (equivalent to adding 1 << (current level - 1)).

Code

Here’s the implementation of the above strategy in Python:

def grayCode(n):
    # Base case for zero bits
    result = [0]
    
    for i in range(n):
        # Reflect the current sequence
        reflected = [x | (1 << i) for x in reversed(result)]
        # Extend the original sequence with the reflected sequence
        result.extend(reflected)
    
    return result

Explanation:

  1. Initialization: We start with [0] for n = 0.
  2. First Iteration (i=0, for n=1):
    • Current sequence: [0]
    • Reflect and append: [0] -> Reflect -> [0] -> Append 1 << 0 to the reflected part -> [1]
    • New sequence: [0, 1]
  3. Second Iteration (i=1, for n=2):
    • Current sequence: [0, 1]
    • Reflect and append: [1, 0] -> Append 1 << 1 -> New values: [3, 2]
    • New sequence: [0, 1, 3, 2]

This process continues until all levels are processed.

Time Complexity

The algorithm has a time complexity of O(2^n):

Thus, combining these facts, the overall time complexity is O(2^n).

Try our interview co-pilot at AlgoAdvance.com