89. Gray Code #

Problem #

The 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, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

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

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

Problem Summary #

Gray code is a binary numeral system in which two consecutive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print its gray code sequence. A gray code sequence must begin with 0.

Solution Ideas #

• Output the n-bit gray code
• Gray code generation rule: take the gray code with binary value 0 as the zeroth item; for the first change, change the rightmost bit; for the second change, change the bit to the left of the first bit that is 1 from the right; for the third and fourth changes, use the same methods as the first and second, and repeat in this way to arrange the gray code of n bits.
• You can simulate it directly, or solve it recursively.

Code #

package leetcode

// Solution 1: recursive method, with relatively optimal time and space complexity
func grayCode(n int) []int {
	if n == 0 {
		return []int{0}
	}
	res := []int{}
	num := make([]int, n)
	generateGrayCode(int(1<<uint(n)), 0, &num, &res)
	return res
}

func generateGrayCode(n, step int, num *[]int, res *[]int) {
	if n == 0 {
		return
	}
	*res = append(*res, convertBinary(*num))

	if step%2 == 0 {
		(*num)[len(*num)-1] = flipGrayCode((*num)[len(*num)-1])
	} else {
		index := len(*num) - 1
		for ; index >= 0; index-- {
			if (*num)[index] == 1 {
				break
			}
		}
		if index == 0 {
			(*num)[len(*num)-1] = flipGrayCode((*num)[len(*num)-1])
		} else {
			(*num)[index-1] = flipGrayCode((*num)[index-1])
		}
	}
	generateGrayCode(n-1, step+1, num, res)
	return
}

func convertBinary(num []int) int {
	res, rad := 0, 1
	for i := len(num) - 1; i >= 0; i-- {
		res += num[i] * rad
		rad *= 2
	}
	return res
}

func flipGrayCode(num int) int {
	if num == 0 {
		return 1
	}
	return 0
}

// Solution 2: literal translation
func grayCode1(n int) []int {
	var l uint = 1 << uint(n)
	out := make([]int, l)
	for i := uint(0); i < l; i++ {
		out[i] = int((i >> 1) ^ i)
	}
	return out
}