PROBLEM DESCRIPTION
An n-bit gray code sequence is a sequence of 2n integers where:
- Every integer is in the inclusive range [0, 2n - 1],
- The first integer is 0,
- An integer appears no more than once in the sequence,
- The binary representation of every pair of adjacent integers differs by exactly one bit, and
- The binary representation of the first and last integers differs by exactly one bit.
Given an integer n, return any valid n-bit gray code sequence.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public List<Integer> grayCode(int n) {
//base condition: for n=0, the result is only 0
if(n == 0){
List<Integer> list = new ArrayList<>();
list.add(0);
return list;
}
//get the answer for n-1
List<Integer> list = grayCode(n-1);
//answer list
List<Integer> ans = new ArrayList<>();
//the first half will be same as for n-1
for(int i=0; i<list.size(); i++){
ans.add(list.get(i));
}
//the second half will be sum of previous + 2^n-1, as we are include a set bit at the MSB position n-1
//we need to do this in reverse so that the difference between the bits is not more than 1, to follow the gray code
for(int i=list.size()-1; i>=0; i--){
ans.add(list.get(i) + (1<<n-1));
}
return ans;
}
}