A solution without a "trick"


  • 0
    A

    On each step change exactly one bit and add it if it is not already contained in the set. Gives the same order as the "trick" solution if you try the LSB first

       public List<Integer> grayCode(int n) {
            if (n < 0) return new ArrayList<>();
            Set<Integer> set = new HashSet<>();
            List<Integer> result = new ArrayList<>();
            set.add(0);
            result.add(0);
            int current = 0;
            int full = (int) Math.pow(2, n);
            while (set.size() != full) {
                for (int bit=0; bit < n; bit++) {
                    current = flip(current, bit);
                    if (!set.contains(current)) {
                        set.add(current);
                        result.add(current);
                        break;
                    } else {
                        current = flip(current, bit);
                    }
                }
            }
            return result;
        }
        
        private int flip(int current, int bit) {
            return (1 << bit) ^ current;
        }
    

Log in to reply
 

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