Problem
The gray code is a binary numeral system where two successive values differ in only one bit.Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
000 - 0
001 - 1
011 - 3
010 - 2
+
110 - 6
111 - 7
101 - 5
100 - 4
Note:
For a given n, a gray code sequence is not uniquely defined.
Solution
The following observation is the key for solving it:[0,1] -> [00, 01] [11, 10] -> [000, 001, 011, 010] [110, 111, 101, 100]
Start from sequence [0, 1], the next sequence has two halves, the first half, is to append 0 at the beginning [00, 01], which have the same value as before. The second half is append 1 before the mirror array of [0, 1], which is 10 | [1, 0] = [11, 10].
import java.util.*;
class GrayCode {
public static List<Integer> grayCodeSeq(int n) {
List<Integer> seq = new ArrayList<>();
seq.add(0);
seq.add(1);
for(int i = 1; i < n; i++) {
int sz = seq.size();
for(int j = sz-1; j >= 0; j--) {
int next = seq.get(j) | (1 << i);
seq.add(next);
}
}
return seq;
}
public static void main(String...args) {
grayCodeSeq(3).stream().forEach(i -> System.out.print(i + ","));
}
}
class GrayCode {
public static List<Integer> grayCodeSeq(int n) {
List<Integer> seq = new ArrayList<>();
seq.add(0);
seq.add(1);
for(int i = 1; i < n; i++) {
int sz = seq.size();
for(int j = sz-1; j >= 0; j--) {
int next = seq.get(j) | (1 << i);
seq.add(next);
}
}
return seq;
}
public static void main(String...args) {
grayCodeSeq(3).stream().forEach(i -> System.out.print(i + ","));
}
}
The time cost is O(2^n), the space is O(2^n) as well.
