Simple Python3 recursive solution, O(2^n) time complexity


  • 0
    D

    There is a nice pattern when going from n-1 to n. Let us begin with n = 1,
    where the only option is:

    0
    1

    Now, let us leverage this sequence for n = 2. One way of doing that,
    is to first generate the first half of the new sequence by prefixing with
    zero the n-1 sequence:

    00
    01

    And for the second half, we suspect that the prefix will be one; but what
    about the rest? we can not just put:

    00
    01
    10
    11

    Cause between snd and trd elements there is more than one bit of difference.
    But we notice that if we reverse the n-1 sequence, the constraints are met:

    00
    01
    11
    10

    Let us repeat the exercise for n = 3, first duplicate the n-1 sequence: first
    occurrence (half) in same order and second one reversed.

    00
    01
    11
    10
    10
    11
    01
    00

    Now we just prefix first and second halves with zero and one respectively:

    000
    001
    011
    010
    110
    111
    101
    100

    Same thing occurs for n = 4:

    0000
    0001
    0011
    0010
    0110
    0111
    0101
    0100
    1100
    1101
    1111
    1110
    1010
    1011
    1001
    1000

    Why this works? Is sort of divide and conquer strategy: once we have the n-1
    sequence, and we know that its reverse its also another gray code for n-1.
    Putting a constant prefix to either sequence will not alter its "gray-codeness"
    nature, as that prefix will remain constant (the other n-1 bits are the ones
    changing).

    The only trick is the transition between the two halves, where we repeat the
    same element. That gets solved by the difference in prefixes, as that is the
    only moment where that first bit changes.

    Time complexity is given by recursive definition:

    T(0) = 1
    T(1) = 2
    T(n) = 2 * T(n-1)

    The last equation is a "linear first order homogeneous difference equation" of
    the form:

    aT(n) + bT(n-1) = 0

    whose general solution is given by:

    T(n) = C*(-b/a)^n

    where C is determined by initial conditions. Applying to our example
    with a=1 and b=-2, leads us to the generic solution of:

    T(n) = C * 2^n

    We could apply one of the base cases of recursion as initial condition, eg

    T(1) = 2

    and substitute to find the C:

    2 = C * 2^1 = 2 * C ==> C = 1

    same result should lead with the other initial condition:

    T(0) = 1 = C * 2^0 = C ==> C = 1

    Therefore our complexity function is just

    T(n) = 2^n

    which is clearly O(2^n)

    Note: we could have concluded that since we got the form T(n) = C * 2^n, but
    is always nice to review this type of material (I kinda forgot it).

    class Solution(object):
        def grayCode(self, n):
            if n <= 0:
                return [0]
            elif n == 1:
                return [0, 1]
            else:
                half0 = self.grayCode(n - 1)
                half1 = [(1 << (n - 1)) | x for x in reversed(half0)]
                return half0 + half1
    

Log in to reply
 

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