Gray Code LeetCode

What is gray code?

Gray code is a binary sequence in which two consecutive values vary by one bit. In this Answer, we’ll explore the problem statement, the solution, and a quiz to strengthen the understanding of this math related problem. Gray codes have gained recognition for their use in rotary encoders, such as those found in computer peripherals like mice. These codes precisely detect positional changes by assigning an exclusive binary sequence that changes per movement one bit at a time. Creating sequences like the binary-reflected gray code algorithm involves bit manipulation, which is important for electronic devices and error correction coding protocols used during data transmission procedures.

Key takeaways
Learn the concept of gray code, a binary sequence where consecutive values differ by only one bit.
Understand the importance of gray code in fields like error correction, data transmission, and rotary encoders.
Explore how to generate the n-bit gray code sequence using an algorithm that builds on smaller sequences.
See a step-by-step Python implementation of the algorithm with clear explanations of each part, including bit manipulation techniques.
Gain insights into the complexity analysis of the solution, understanding its efficiency and trade-offs for different input sizes.

Problem statement

In this problem, provided any integer n, we need to return any n-bit gray code sequence. A gray code sequence should abide by the following constraints:

It should comprise 2ⁿ integers.
Our first value is 0.
Each integer is in the [0, 2ⁿ - 1] range.
There are no repeating integers in the sequence.
The binary representation of adjacent integers varies by one bit.
The binary representation of our first and last integers varies by one bit.

An example of a gray code sequence can be seen below:

Solution to the gray code problem

This algorithm aims to generate gray code sequences of length n by constructing the sequence based on previously computed values, incorporating Math concepts for computation. It starts with a base case n = 0, returning [0]. For n > 0, it initializes a sequence [0, 1], then iterates from i=2 to n to extend the sequence. Each iteration reverses the current sequence and calculates a prefix value using bit manipulation techniques, specifically bitwise left-shifting. This prefix is added to each element in the reversed sequence, extending the result and generating the subsequent gray code sequence. The algorithm gradually constructs longer sequences through an iterative approach, resulting in a final list representing the gray code sequence for the given n value.

Educative-99 helps you solve complex coding problems like the gray code problem by teaching you to recognize patterns and apply the right algorithms.

Code example

The code for this problem is provided below:

def gray_code(n):
    # Base case: If n is 0, the only gray code is [0].
    if n == 0:
        return [0]
    
    # Initialize the result list for n = 1, which is [0, 1].
    result = [0, 1]
    
    # Loop through to generate gray codes for 2 to n bits.
    for i in range(2, n + 1):
        # Create a reversed copy of the current result sequence.
        sequence = result[::-1]
        
        # Compute the prefix for the new gray code values (1 shifted left by i-1).
        prefix = 1 << (i - 1)
        
        # Extend the result with new values created by adding the prefix
        # to each element in the reversed sequence.
        result.extend([prefix + num for num in sequence])
    
    # Return the final gray code sequence.
    return result
# Driver code
n = [3,1,0,4,2]
for i in range(len(n)):
  print(i+1,".\t n: ", n[i])
  print("\t Gray code: ", gray_code(n[i]))
  print("-"*100)

Notice that the gray code sequence is symmetric. The second half of the sequence is a mirror of the first half, but with the leading bit set to 1.

Code explanation

Lines 3–4: The base case to check if n is 0. Return [0] in this case.
Line 7: We initialize result, which stores the gray code sequence to [0,1] (an initial 1-bit gray code sequence).
Line 10: This is the loop to extend the result list with each iteration.
Line 12: We reverse result to obtain a reversed version of the previous sequence. Our new n bit sequence should be generated by taking the reverse of the n-1 bit sequence and adding 1 as a prefix.
Line 15: We define our prefix, which is to be added to the reversed sequence. This value is calculated by left-shifting 1 by i-1 positions, which makes sure that our sequence begins with 1.
Line 19: This extends result by appending the sequence list after the addition of the prefix. We have now generated a new gray code sequence based on the prior sequence n-1.
Line 22: This returns our gray code sequence.

To learn more about the mathematical logic algorithms, consider checking out our extensive course Grokking Coding Interview Patterns. It covers more than 20 algorithmic patterns and has 230+ problems.

Time complexity

The time complexity of the gray code algorithm is $O(n^{2})$ where $n$ is the input parameter representing the length of the gray code sequence, as the algorithm constructs the sequence by doubling the number of elements at each iteration, resulting in exponential growth relative to $n$ .

Space complexity

The space complexity of this code is $O(2^n)$ since we store sequences that are of length $2^n$ , which is proportional to the input $n$ . This leads to exponential space usage.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

How is bit manipulation used in generating gray code?

Bit manipulation is used in gray code generation to efficiently create new numbers. For example, to add a new bit, the existing sequence is mirrored, and a bit is set using 1 << (i - 1) (left-shift operator), which allows precise control over individual bits.

What are some common bit manipulation techniques used in programming?

Some common bit manipulation techniques include:

Left Shift (<<): Shifts bits to the left, effectively multiplying the number by powers of 2.
Right Shift (>>): Shifts bits to the right, dividing the number by powers of 2.
Bitwise AND (&): Compares bits and returns 1 if both are 1.
Bitwise OR (|): Compares bits and returns 1 if at least one is 1.
Bitwise XOR (^): Returns 1 if bits are different.
Bitwise NOT (~): Inverts the bits (flips 1 to 0 and vice versa).

What is the difference between gray code and binary code?

The key difference is that in gray code, two consecutive numbers differ by only one bit, while in binary code, multiple bits can change between consecutive numbers. This makes gray code useful in systems that are sensitive to signal transitions.

Free Resources