An iterative Python solution based on Gray Code definition


  • 0
    G

    The binary-reflected Gray code list for n bits can be generated recursively from the list for n−1 bits by reflecting the list (i.e. listing the entries in reverse order), concatenating the original list with the reversed list, prefixing the entries in the original list with a binary 0, and then prefixing the entries in the reflected list with a binary 1.[6] For example, generating the n = 3 list from the n = 2 list:

    2-bit list: 00, 01, 11, 10

    Reflected: 10, 11, 01, 00

    Prefix old entries with 0: 000, 001, 011, 010,

    Prefix new entries with 1: 110, 111, 101, 100

    Concatenated: 000, 001, 011, 010, 110, 111, 101, 100

    class Solution:
        # @param {integer} n
        # @return {integer[]}
        # 9:25
        BASE = ['0', '1']
    
        def grayCode(self, n):
            if n == 0:
                return [0]
    
            result = Solution.BASE
            for i in range(n - 1):
                left = map(lambda x: '0' + x, result)
                right = map(lambda x: '1' + x, result[::-1])
                result = left + right
    
            return map(lambda x: int(x, 2), result)

  • 0
    C

    Smart idea, based on your idea, here is an improved version while the grayCode is not treated as string but numerical number :

    def grayCode(self, n):
        res = [0]
        for i in xrange(n):
            res += map(lambda x:2**i+x, [x for x in res[::-1]])
        return res
    

  • 0

    Why not just this?

    def grayCode(self, n):
        res = [0]
        for i in xrange(n):
            res += (2**i+x for x in res[::-1])
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.