Posts Gray Code
Post
Cancel

Gray Code

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.

leetcode

SOLUTION

snapshot

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;

    }

}
This post is licensed under CC BY 4.0 by the author.