Gray Code

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

                                            
import java.util.*;

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

                                            
class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        result = []
        for i in range(2**n):
            result.append((i >> 1) ^ i)
        return result

                                            
/**
 * Note: The returned array must be malloced, assume 
caller calls free().
 */
int* grayCode(int n, int* returnSize){
    *returnSize = 1 << n;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    for (int i = 0; i < *returnSize; i++) {
        result[i] = i ^ (i >> 1);
    }
    return result;
}

                                            
public class Solution {
    public IList<int> GrayCode(int n) {
        IList<int> result = new List<int>();
        
        for (int i = 0; i < 1 << n; i++) {
            result.Add(i ^ i >> 1);
        }
        
        return result;
    }
}

                                            
/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
    let result = [];
    for (let i = 0; i < Math.pow(2, n); i++) {
        result.push(i ^ (i >> 1));
    }
    return result;
};

                                            
function grayCode(n: number): number[] {
    const result: number[] = [0];
    for (let i = 0; i < n; i++) {
        const len = result.length;
        for (let j = len - 1; j >= 0; j--) {
            result.push(result[j] | 1 << i);
        }
    }
    return result;
};

                                            
class Solution {
    /**
     * @param Integer $n
     */
    function grayCode($n) {
        $result = [];
        for ($i = 0; $i < 1 << $n; $i++) {
            $result[] = $i ^ $i >> 1;
        }
        return $result;
    }
}

                                            
class Solution {
    func grayCode(_ n: Int) -> [Int] {
        var result: [Int] = []
        for i in 0..<(1 << n) {
            result.append(i ^ (i >> 1))
        }
        return result
    }
}

                                            
class Solution {
    fun grayCode(n: Int): List<Int> {
        val result = mutableListOf<Int>()
        for (i in 0 until (1 shl n)) {
            result.add(i xor (i shr 1))
        }
        return result
    }
}

                                            
class Solution {
  List<int> grayCode(int n) {
    List<int> result = [];
    for (int i = 0; i < (1 << n); i++) {
      result.add(i ^ (i >> 1));
    }
    return result;
  }
}

                                            
func grayCode(n int) []int {
    res := make([]int, 1<<uint(n))
    for i := 0; i < 1<<uint(n); i++ {
        res[i] = i ^ i>>1
    }
    return res
}

                                            
# @param {Integer} n
# @return {Integer[]}
def gray_code(n)
    result = [0]
    (0...n).each do |i|
        result += result.reverse.map { |x| x | 1 << i }
    end
    return result
end

                                            
object Solution {
    def grayCode(n: Int): List[Int] = {
        if (n == 0) {
            List(0)
        } else {
            val half = grayCode(n - 1)
            half ++ half.reverse.map(_ | 1 << (n - 1))
        }
    }
}

                                            
impl Solution {
    pub fn gray_code(n: i32) -> Vec<i32> {
        let mut result = Vec::new();
        for i in 0..1 << n {
            result.push(i ^ (i >> 1));
        }
        result
    }
}

To solve this coding challenge, we need to generate an n-bit Gray code sequence that satisfies the given conditions. Let's break down the problem and understand the requirements before moving to the detailed steps.

Explanation:

Gray Code is a binary numeral system where two successive values differ in only one bit. Given an integer \( n \), we need to generate a sequence of numbers such that:

Each number is in the range \([0, 2^n - 1]\).
The first number in the sequence is 0.
Each number appears at most once in the sequence.
The binary representation of every pair of adjacent numbers differs by exactly one bit.
The binary representation of the first and last numbers also differ by exactly one bit.

A Gray code sequence can be constructed using the formula: \( Gray(i) = i \oplus (i >> 1) \), where \( \oplus \) denotes the bitwise XOR operation and \( >> \) the right shift.

This formula ensures that each number in the sequence differs from the previous one by only one bit.

Step-by-Step Explanation:

Initialization :

Determine the total number of elements in the Gray code sequence for \( n \) bits, which is \( 2^n \).
Initialize an empty list called
result

to store the sequence.

Generate Gray Code :

Iterate over all integers from 0 to \( 2^n - 1 \).
For each integer \( i \), calculate the Gray code using the formula \( i \oplus (i >> 1) \).
Append the result to the
result

list.

Return the Result :

After generating all Gray codes, return the
result

list as the final sequence.

Detailed Steps in Pseudocode:

                                            
# Initialize the number of elements in the Gray code sequence
total_elements = 2^n

# Initialize an empty list to store the Gray code sequence
result = []

# Loop over each integer from 0 to total_elements - 1
FOR i FROM 0 TO total_elements - 1 DO
    # Calculate the Gray code for the current integer
    gray_code = i XOR (i >> 1)
    
    # Append the Gray code to the result list
    APPEND gray_code TO result
END FOR

# Return the final Gray code sequence
RETURN result

Explanation of the Pseudocode:

total_elements = 2^n : This step determines that the total number of Gray codes for an n-bit sequence is \( 2^n \).
result = [] : We initialize an empty list to store the sequence.
FOR i FROM 0 TO total_elements - 1 : Iterate over all integers from 0 to \( 2^n - 1 \).
gray_code = i XOR (i >> 1) : For each integer \( i \), calculate its Gray code representation by using the bitwise XOR of \( i \) and \( i \) right-shifted by 1.
APPEND gray_code TO result : Append the calculated Gray code to the
result

list.
RETURN result : After completing the loop, return the
result

list, which now contains the Gray code sequence.

By following these detailed steps and the given pseudocode, you will be able to generate a valid n-bit Gray code sequence that meets all the specified conditions.