16.10: gray code improvements

#1

Hi guys,

the improved solution to gray code generation says

… Gray code property being violated from 010 to 100. However, it is preserved everywhere else.

The property also doesn’t hold for wrap around: from 110 to 000.

I also have some suggestion about the code. The condition

if (numBits == 1) {
return Arrays.asList(0, 1);
}

is unnecessary, since you can build from the solution of 0 bits.

You also create a new ArrayList on each iteration. Since we don’t need to keep the solution to (n-1) problem, we can just modify that solution and return it.
Note that you have to replace Arrays.asList(0) to new ArrayList<>(Arrays.asList(0)) to allow adding new elements to it. Something like this:

public static List<Integer> generateGrayCode(int n) {
    if (n == 0) {
        return new ArrayList<>(Arrays.asList(0));
    }

    List<Integer> previous = generateGrayCode(n - 1);

    for (int i = previous.size() - 1; i >= 0; i--) {
        previous.add(previous.get(i) | (1 << (n - 1)));
    }

    return previous;
}
0 Likes
#2

I have a related question about the Gray code problem. Is it really O(n2ⁿ)?

Here’s an iterative solution. It seems like it is O(2ⁿ) as it just enumerating all 2ⁿ elements. There isn’t O(n) work happening per element.

class GrayCode {
    List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0); if (n == 0) return result;
        result.add(1); if (n == 1) return result;
        int i = 1;

        while (i < n) {
            for (int j = result.size() - 1; j >= 0; j--) {
                int next = result.get(j) | (1 << i);
                result.add(next);
            }

            i += 1;
        }

        return result;
    }
}
0 Likes
#3

Hey @damluar,

Many thanks for this improvements, and it is definitely a more succinct code with a little loss of readability. Personally I like your for sure. Will update that in the future edition.

0 Likes
#4

Hey @sourcedelica,

You are right, we update the time complexity as O(2^n) in the later edition.

0 Likes