Friday, May 23, 2014

Leetcode (Python): Gray Code

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.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

Solution:

class Solution:
    # @return a list of integers
    def grayCode(self, n):
        used =[]
        solution =[]
        for i in range(0,2**n):
            used.append(False)
        self.grayCodeRec(0, n, used, solution)
        return solution
        
    def grayCodeRec(self, num, n, used, solution):
        solution.append(num)
        used[num] = True
        if len(solution)==2**n:
            return True
        for i in range(0,n):
            num2 = num ^ (1<<i)
            if not used[num2] and self.grayCodeRec(num2, n, used, solution):
                return True
        used[num] = False
        solution.pop()
        return False

No comments :

Post a Comment