Easy-to-understand O(2^n) JAVA Solution with Explanation


  • 0
    Y

    gray code is also knows as reflected binary code

    when n is 1:
    gray binary - decimal it represents
    0 - 0
    1 - 1
    when n is 2, the first half from n = 1keeps in the order, the second half reverse and then add 2 * (n - 1) to each element
    gray binary(n - 1) - gray code(n) - decimal it represents
    0 - 00 - 0
    1 - 01 - 1
    1 - 11(1 + 2) - 2
    0 - 10(0 + 2) - 3
    it will be the same from i - 1 to i (1 <= i <= n)
    so we can use this feature to solve this problem

    For each i, it will run 2*(i -1) operations
    The total operations will be 2 + 2^2 + 2^3 + 2^4 + ... + 2^(n -1) = 2^n - 2
    Therefore the time complexity is O(2^n)

    public class Solution {
     public List<Integer> grayCode(int n) {
            List<Integer> grayCodeDecimal = new ArrayList<>();
            if (n < 0) {
                return grayCodeDecimal;
            }
            if (n == 0) {
                grayCodeDecimal.add(0);
                return grayCodeDecimal;
            }
            for (int i = 1; i <= n; ++i) {
                if (i == 1) {
                    grayCodeDecimal.add(0);
                    grayCodeDecimal.add(1);
                } else {
                    int base = (int) Math.pow(2, i - 1);
                    for (int j = base - 1; j >= 0; --j) {
                        grayCodeDecimal.add(base + grayCodeDecimal.get(j));
                    }
                }
            }
            return grayCodeDecimal;
        }
    }
    

Log in to reply
 

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