An accepted three line solution in JAVA


  • 136
    J
    public List<Integer> grayCode(int n) {
        List<Integer> result = new LinkedList<>();
        for (int i = 0; i < 1<<n; i++) result.add(i ^ i>>1);
        return result;
    }
    

    The idea is simple. G(i) = i^ (i/2).


  • 0
    J

    Great solution. Could you explain why?


  • 5
    S

    Yes, how to figure out this bit control, I cannot come up with it


  • 38
    D

    Just added information for those who are interested (all credited to Wiki gray code

    /*
            The purpose of this function is to convert an unsigned
            binary number to reflected binary Gray code.
     
            The operator >> is shift right. The operator ^ is exclusive or.
    */
    unsigned int binaryToGray(unsigned int num)
    {
            return (num >> 1) ^ num;
    }
     
    /*
            The purpose of this function is to convert a reflected binary
            Gray code number to a binary number.
    */
    unsigned int grayToBinary(unsigned int num)
    {
        unsigned int mask;
        for (mask = num >> 1; mask != 0; mask = mask >> 1)
        {
            num = num ^ mask;
        }
        return num;
    }
    

  • 0
    Z

    Great solution..BTW can you provide the correctness of the formula. I couldn't find it on Google either.


  • 0
    M

    That is really amazing, but could you please explain why it works?


  • 0
    H

    Good explanation. Thanks.


  • 30
    F

    The solution is great, but this problem sucks. How is anyone supposed to come up with such an idea in an interview, if he's never encountered this problem before?


  • 0
    S

    I understand how this works, but I don't know why this works...


  • 40
    W

    I don't know how to come up with the solution i^(i>>1), but I will try to explain why it works.

    Adding one to a number results in flipping all the bits from the rightmost zero bit to the end, e.g. 110011 + 1 = 110100

    In the general form, i = ...?01...1, i+1 = ...?10...0, ? represents the left bit of the rightmost zero bit, the length of tailing one bits of i is the same as the length of tailing 0 bits of i+1, and the bits from the beginning to the ? are the same.

    Then i^(i>>1) = xxx(?^0)10...0, (i+1)^((i+1)>>1) = xxx(?^1)10...0. Since the bits from the beginning to the ? are the same, xxx part of both results must be same, it's obvious the tailing parts of 10...0 must be same, and its length is the same as the length of tailing one bits of i, so there is only one bit difference comes from (?^0) and (?^1).


  • 0
    T

    @sqrl You can refer to Gray Code.
    I think this explanation in wikipedia is clear.


  • 1

    @jinrf Beautiful!


  • 0
    S

    It's beautiful
    @Fanchao I don't know this idea and build another more complicated solution, but it works.


  • 1
    A

    @Fanchao

    You don't need to know what Grey Code is nor bit* operations. You can simply do the following equivalent algorithm:

    int x = 2;
    for(int i=0; i<n-1; i++) {
        for(int j=grayCodeList.size()-1; j>=0; j--) 
            grayCodeList.add(grayCodeList.get(j) + x);
        x *=2;       
    }

  • 0
    N

    I think you provide incomplete code.
    grayCodeList cannot be empty before you try to call get()

    @angarita said in An accepted three line solution in JAVA:

    You don't need to know what Grey Code is nor bit* operations. You can simply do the following equivalent algorithm:
    int x = 2;
    for(int i=0; i<n-1; i++) {
    for(int j=grayCodeList.size()-1; j>=0; j--)
    grayCodeList.add(grayCodeList.get(j) + x);
    x *=2;
    }


  • 0
    A

    @newdev You're right. This code is for n>=2 and the list already contains elements 0 and 1


  • 0
    A

    @jinrf
    one of the great solution i have ever met..thanks


  • 0
    D

    Although this solution blows my mind it is not valid for an interview scenario.
    It is almost impossible to come up with this on the fly without ever seeing this problem before.


Log in to reply
 

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