We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Gray Code

Number: 89

Difficulty: Medium

Paid? No

Companies: IBM, Google, Apple, Bloomberg, Amazon

Problem Description

Generate an n-bit Gray Code sequence of 2^n integers such that:

  • Every integer is within the range [0, 2^n - 1].
  • The first integer is 0.
  • Each integer appears no more than once.
  • The binary representation of every pair of adjacent integers differs by exactly one bit.
  • The binary representation of the first and last integers also differs by exactly one bit.

Key Insights

  • The total number of gray code values is 2^n.
  • The i-th Gray code can be computed using the formula: gray = i XOR (i >> 1).
  • The XOR operation between i and i shifted right by 1 ensures that consecutive numbers differ by exactly one bit.
  • This approach uses bit manipulation and avoids the complexity of recursion or backtracking.

Space and Time Complexity

Time Complexity: O(2^n) — we iterate through all 2^n numbers. Space Complexity: O(2^n) — we store all 2^n gray code values in a list or array.

Solution

We solve the problem by leveraging a formula to generate Gray code values without explicitly performing backtracking. For each integer i from 0 to 2^n - 1, we compute its corresponding Gray code using the formula:

gray = i XOR (i >> 1)

This bit manipulation technique guarantees that each computed Gray code will have a one-bit difference with its predecessor. We store these values in an output array or list and return it.

Data Structures used:

  • A list (or array) to store the sequence.

Algorithm:

  1. Compute the total count as 2^n (using left shift).
  2. Iterate from 0 up to 2^n - 1.
  3. For each i, calculate the Gray code using i XOR (i >> 1).
  4. Append the result to the list.
  5. Return the resulting list.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to generate Gray Code sequence for n bits
def grayCode(n):
    # Calculate total number of elements: 2^n
    total_numbers = 1 << n  # left shift operation
    result = []  # List to store the Gray Code sequence
    
    # Iterate through each number from 0 to 2^n - 1
    for i in range(total_numbers):
        # Calculate Gray code by XORing the number with its right shifted version
        gray = i ^ (i >> 1)
        result.append(gray)  # Append the computed Gray code to the result list
    
    return result

# Example usage
print(grayCode(2))  # Expected Output: [0, 1, 3, 2]
← Back to All Questions