Notes to myself for gray code


  • 0
    S
    public class Solution {
      /*
      Understanding the gray code , since we have to just change 1 bit
       sequence for n = 1 is obvious
       0, 1
       sequence for n = 2
           lets start with sequence of n = 1
           0, 1 for n = 2 we will need to add another bit to the left of these sequence.
           so can we make 10, 11 (by adding second bit to previus sequence)?  no we cant because sequence will become
           00, 01, 10 (this is wrong because we changed 2 bits while we are allowed to change only one bit), 11 
           
           so start backwards, do not change the right bits and add 1 at second bit position, then go backwards as now the new msb is already added, and every previous number is 1 bit away only.
           so we get 
           00, 01 , 11 (we added second bit to 01), 10 (then we added second bit to 00, this only changes one bit as 00 was 1 away from 01 - the lsb and msb has been set just before this element so that remains same), 
           
           so to summarize:  we appended 1 on the left but by traversing backwards in existing sequence that we had.
           
           when we are done, now for n = 3
           we add third bit , to 00,01,11,10 , but again backwards so we get  110,111,101,100 
           sequence is now  000, 001, 011, 010, 110 , 111,101,100
           
           so recap
           we took 
           0
           we added 2^0 ie 1 to get 0, 1
           
           now we take 0, 1
           we added 2^1 = 10 to 1, 0 (remember we are adding in reverse order so we only change one bit backwards)
           so we get 11,10
           sequence is 00,01,11,10
           
           now we take 00,01,11,10
           we add 2^2  i.e 100 to 10,11,01,00 (again note reverse of the series)
           we get 110,111,101,100
           sequence is 000,001,011,010,110,111,101,100
      
      */
        public List<Integer> grayCode(int n) {
            List<Integer> result = new ArrayList<>();
            result.add(0);
            for(int i = 0; i < n; i++){
                int increment = 1 << i;
                for(int j = result.size()-1; j >= 0; j--){
                    result.add(result.get(j) + increment);
                }
            }
            return result;
        }
    }

Log in to reply
 

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