menu

[LeetCode] 089. Gray Code *

Problem (Medium)

089. 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.

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 = 2^n, which for n = 0 the size is 2^0 = 1.
  • Therefore, for n = 0 the gray code sequence is [0].

Approach 1: LeetCode yuyibestman

Idea

bit operation solution

My idea is to generate the sequence iteratively. For example, when n=3, we can get the result based on n=2. 00,01,11,10 -> (000,001,011,010 ) (110,111,101,100). The middle two numbers only differ at their highest bit, while the rest numbers of part two are exactly symmetric of part one. It is easy to see its correctness.

Solution

class Solution1:
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        res = [0]
        for i in range(n):
            for j in range(len(res)-1, -1, -1):
                res.append(res[j] | 1 << i)
        return res

Complexity

  • Time: $O()$
  • Space: $O()$

Approach 2: Solution from byronyi

Idea

One-liner Python solution (with demo in comments)

All you need is a bit of careful thought.

Btw, it’s extremely useful to write down your thought/demo in comments before you actually start to write the code, especially during interview.

Even if you do not solve the problem finally, the interviewer at least get to know what you’re thinking.

And if you don’t get the problem right, he/she will have a chance to correct you.

Solution

class Solution2:
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]

        from up to down, then left to right

        0   1   11  110
                10  111
                    101
                    100

        start:      [0]
        i = 0:      [0, 1]
        i = 1:      [0, 1, 3, 2]
        i = 2:      [0, 1, 3, 2, 6, 7, 5, 4]
        """
        res = [0]
        for i in range(n):
            res += [x + pow(2, i) for x in reversed(res)]
        return res

Complexity

  • Time: $O()$
  • Space: $O()$



KF

Comments