Simple Java Solution based on observation


  • 0
    G
    public class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> prev = new LinkedList<>();
            prev.add(0);
            if(n == 0){
                return prev;
            }
    
            List<Integer> current = new LinkedList<>();
            for(int i = 1; i <= n; i++){
                for(int j=0; j<prev.size(); j++){
                    int temp = prev.get(j)<<1;
                    // alternate 0 and 1 for each previous sequence
                    if(j%2 == 0){
                        current.add(temp);
                        current.add(temp+1);
                    }else{
                        current.add(temp+1);
                        current.add(temp);
                    }
                }
    
                prev = current;
                current = new LinkedList<>();
            }
            
            return prev;
        }
    }

  • 0
    T

    What is that observation?


  • 0
    G

    I believe the observation is that the nth sequence and the n+1th sequence always have one digit in difference, therefore we can left shift the nth sequence, add 0 then 1; left shift the n+1th sequence, add 1 then 0 to generate new sequences that still only differ in one digit. Try it out with some examples. (0,1), (00, 01, 11, 10),(000,001,011,010,110,111,101,100). Does it make sense?


  • 0
    T

    Oh I missed the shift, so it's like taking the existing reversed and adding a 1 at the beginning just adding doing it from the back and having some magic property of this "recursion" help to keep the order.

    Thank, you I see the pattern, but not the why, yet.


Log in to reply
 

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