What if I have no knowledge over Gray Code before?


  • 27
    W

    A simple Google search will reveal the secret behind Gray Code, of course. Knowing the formula, this question can be solved within 5 minutes. But what if I've never known anything about Gray Code? Is it feasible for someone to derive the formula during an interview? I think I would just get stuck for 45 minutes trying to figure out how to generate an algorithm for it. Is this question intended to test one's knowledge base?


  • 3
    L

    Here is my take about Gray codes. Maybe other people might have different opinions.

    1 - You have to know what they are (it was even written in the problem statement)

    The gray code is a binary numeral system where two successive values
    differ in only one bit.

    2 - You have to know what they are useful for.

    3 - You have to know that they are "symmetric".

    With 1 and 3, you can solve any programming problem about Gray code you could have in an interview. I don't think anyone expect you to know the ins-and-outs of the Gray code (well, unless you're applying to a computer architecture position), but people expect you to be able to derive algorithms from 1 and 3.
    The point 2. is a nice touch to tell your interviewer.


  • 84
    H

    I agree with loick. I don't think it's a knowledge base problem. It's also my first time to hear about Gray Code. But after trying some small cases, I still figured out an algorithm for it.

    From my intuition, the problem is like Hanoi. If you're able to solve n = 2 case, then you can kind of repeat it twice to achieve n = 3 case. Lets try to extend n = 2 case to n = 3 case first.

    When n = 2, the sequence is
    00 -> 01 -> 11 -> 10
    If you want to extend it to n=3 directly without modifying old part, there are only two possible sequence, and they are not hard to find out.

    000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100

    000 -> 001 -> 011 -> 010 -> 110 -> 100 -> 101 -> 111

    So now, the problem is, which one should we choose. I would choose the first one for two reasons.

    1. The last elements have similar form in both n=2 and n=3 case. They are 1 follows bunch of 0's. Since we hope to extend the same algorithm to n=4 n=5... cases. It's good to preserve some properties.

    2. If we only look at the last 2 digits, we can see that in the first sequence, the second half is exact the reverse of the first half, that means, we can systematically generate the second half according to the first half.

    That's how I figured out the algorithm. Hope that helps!


  • 0
    Z

    I agree. In fact, having not heard of Gray Code before, I had a hard time under standing what "two successive values differ in only one bit means". In my original under standing, the following output should be valid for input n = 3:

    000->010->011->001->101->111->110->100
    

    so I was really not sure which test case will be tested. Thanks to @hslu, I understand what the problem wants and solved it like in 5 minutes. I don't think it has anything to do with mathematical formula.


  • 1
    R

    Though I heard it before, I just in time find another method besides the methods metioned above or in Wikipedia by induction.

    +2^k: i % 2^(k+2) == 2^k
    -2^k: i % 2^(k+2) == 2^k*3
    

    means when i % 2^(k+2) == 2^k, that A[i] - A[i-1] = 2^k;
    when i % 2^(k+2) == 2^k*3, that A[i] - A[i-1] = -2^k;

    No prove, but I pass the OJ.

    Time cost is O(n*2^n) which I believe is the fastest algorithms.


  • 0
    D

    Not really, the fastest algorithm should run in O(2^n).


  • 0
    D

    Indeed, that's the same algorithm I used and it requires no prior knowledge about Gray Code at all. Nice illustration.


  • 0
    R

    But since the number of gray codes need to generate is 2^n.
    And each code's length is n bits.
    The time cost of print them out is already O(n*2^n)


  • 0
    D

    Well, I was talking about the algorithm to generate those numbers, not including printing them out... So generate each number only takes 1 addition operation. So total time cost is roughly O(2^n). I guess we normally refer to computation cost rather than printing cost as the time complexity of algorithm.


  • 0
    B

    It's easy to get 1. I think most one was stuck in 3. That's not so difficult to solve this problem after getting the symmetric rule.


  • 29
    C

    I approached the problem with dynamic programming, or table building.

    n = 1

    0
    1

    n=2

    0 0
    0 1
    1 1
    1 0

    n=3

    0 0 0
    0 0 1
    0 1 1
    0 1 0
    1 1 0
    1 1 1
    1 0 1
    1 0 0

    After growing some rows and cols of the table, you can tell how to build table n+1 from table n, namely add 1 to each row of table n, reverse it and append on table n. The actual operation is easier since the output only requires a list(not a nested list), so adding bit 1 to a table row is just add 1<<(n-1) to the number that row represents.


  • 0
    L

    Thanks for your explain, it's easy to solve after your advice.


  • 1
    I

    I don't have knowledge about gray code, and my first mind is to brute-force it.

    The time complexity is O(n*(2^n)), slightly larger than O(2^n) ^_^

    vector<int> grayCode(int n) {
        unordered_set<int> s{0};
        vector<int> r{0};
        for (int c = 0, i = 1; i < (1<<n); ++i) {
            for (int j = 0; j < n; ++j) {
                if (s.insert(c ^ (1<<j)).second) {
                    r.push_back(c ^= (1<<j));
                    break;
                }
            }
        }
        return r;
    }

  • 0
    Y

    thanks for clarifying. it's easier after reading your post.


  • 0
    V

    That is the idea I used in my solution.


  • 0
    V

    I use the same idea with @hsiu. Here is my python code:

    class Solution:
        # @return a list of integers
        def grayCode(self, n):
            if n ==0:
                return [0]
            ret = [0,1]
            for i in range(1,n):
                ret = ret + [pow(2,i) + ret[x] for x in range(len(ret)-1,-1,-1)]
            return ret

  • 0
    J

    I can't agree more.And I cost one hour = = ....


  • 0
    L

    This is awesome and acute observation!


  • 0

    Actually there are several possible sequences when n=3 instead of just two as you've mentioned; besides I think knowing the formula will definitely increase the possibility of your to hack it more fluently otherwise it will dramatically exhaust your brain. One of the so-called several is as follows:

    000->100->101->111->110->010->011->001


  • 0
    H

    Thanks for point out! So maybe I should say "up to isomorphism". Is that correct? or there's still something else I'm not aware of.


Log in to reply
 

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