XOR solution with buffer, O(2^n) space and time complexity


  • 0
    Z

    public class Solution {

      public List<Integer> grayCode(int n) {
      
        List<Integer> result = new ArrayList<>();
        result.add(0);
        if(n == 0) return result;
        int max = 1<<n;
        boolean buff[] = new boolean[100000];
        int last = result.get(result.size()-1);
        boolean exist = true;
        while(exist){
            exist = false;
            for(int i  =0 ;i<n;i++){
                int bit = 1<<i;
                int cur = last ^ bit;
                if(cur == 0 || buff[cur] || cur == last) continue;
                result.add(cur);
                last = cur;
                exist = true;
                buff[cur] = true;
                break;
            }
        }
        return result;
    }
    

    }


Log in to reply
 

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