Gray Code Sequence - Nth element


  • 1
    M

    For the Nth element in the gray code sequence,
    the following equation can be used

    N ^ floor(N/2)

    Here's my code snippet:

    public List<Integer> grayCode(int n) {
    
    List<Integer> result = new ArrayList<Integer>();
    
    if (n == 0) {
        result.add(0);
        return result;
    }
    
    for (int i = 0; i < Math.pow(2, n); i++) {
        result.add(i ^ (i / 2));
    }
    
    return result;
    }

  • 0
    D

    why does this function make sense?


  • 0
    M

    N B G


    0 000 000 --
    1 001 001 --
    2 010 011 --
    3 011 010 --
    4 100 110 --
    5 101 111 --
    6 110 101 --
    7 111 100 --

    If you look closely, for all the numbers, the most significant 1 bit does not change between binary representation and Gray code representation. The other bits change. So it has to do something with half of that number.

    Most of these bit manipulation problems are based on patterns. Look for patterns in them

    Half of 7 is 3.5 .. Floor it 3... 111 and 011.. XOR them 100 Gray code for 7. This apparently works for all the numbers.

    More details on Gray code (explains concept of mirroring to write Gray code numbers, and the concept very well):
    http://www.eetimes.com/document.asp?doc_id=1274549


  • 0
    D

    Thank you! This is very helpful!


Log in to reply
 

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