Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/89.html

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.

 

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

 

Constraints:

  • 1 <= n <= 16

Algorithm

For n=3:

Int    Grey Code    Binary
 0      000        000
 1      001        001
 2      011        010
 3      010        011
 4      110        100
 5      111        101
 6      101        110
 7      100        111

My idea is using left shifts, and then operate the lowest bit, followed by 0 or 1.

Another idea is to get the highest position directly, and then add all the previous ones to the highest one

  • Note that a for loop starts from 0, if it is n, then <<n-1 is enough
  • The second for loop must be reversed from list-size-1 to 0.

If it starts from 0, then the list keeps getting new homes, the size keeps increasing, and it loops endlessly.

Code

  • import java.util.ArrayList;
    import java.util.List;
    
    public class Gray_Code {
    
    	public static void main(String[] args) {
    		Gray_Code out = new Gray_Code();
    		Solution_optimize_on_highest_digit s = out.new Solution_optimize_on_highest_digit();
    
    		System.out.println(s.grayCode(3)); // output: [0, 1, 3, 2, 6, 7, 5, 4]
    	}
    
    	// 0 => 0,1 => 10,11
    	public class Solution_optimize_on_highest_digit {
    		public List<Integer> grayCode(int n) {
    
    			List<Integer> list = new ArrayList<Integer>();
    
    			list.add(0); // special case
    
    			for (int i = 1; i <= n; i++) {
    				int highestBit = 1 << (i - 1);
    
    				// @note:@memorize: nice cutoff! no need to use an extra tmpList
    				for (int j = list.size() - 1; j >= 0; j--) {
    					list.add(highestBit + list.get(j));
    				}
    			}
    
    			return list;
    		}
    	}
    
    
    	public class Solution_on_highest_digit {
    	    public List<Integer> grayCode(int n) {
    
    	        List<Integer> list = new ArrayList<Integer>();
    
    	        if (n < 0) {
    	            return list;
    	        }
    
    	        // init
    	        list.add(0);
    
    	        // @note: append 1 at highest digit position
    	        for (int i = 1; i <= n; i++) {
    
    	            // int prevLen = list.size();
    	            List<Integer> tmpList = new ArrayList<Integer>(list);
    	            for (int each: list) {
    	                tmpList.add(each + (1 << (i - 1)));
    	            }
    
    	            list = tmpList;
    	        }
    
    	        return list;
    	    }
    	}
    
    
    	public class Solution_on_lowest_digit {
    		public List<Integer> grayCode(int n) {
    
    			List<Integer> list = new ArrayList<Integer>();
    
    			if (n == 0) {
    				list.add(0);
    				return list;
    			}
    
    			list.add(0);
    			list.add(1);
    
    			for (int i = 2; i <= n; i++) {
    
    				List<Integer> allprev = new ArrayList<Integer>(list);
    
    				for (int each : allprev) {
    					each <<= 1;
    
    					if (!list.contains(each))
    						list.add(each);
    					if (!list.contains(each + 1))
    						list.add(each + 1);
    				}
    
    			}
    
    			return list;
    		}
    	}
    
    }
    
    ############
    
    class Solution {
        public List<Integer> grayCode(int n) {
            List<Integer> ans = new ArrayList<>();
            for (int i = 0; i < 1 << n; ++i) {
                ans.add(i ^ (i >> 1));
            }
            return ans;
        }
    }
    
  • // OJ: https://leetcode.com/problems/gray-code/
    // Time: O(2^N)
    // Space: O(2^N)
    class Solution {
    private:
        inline int toggle(int n, int i) {
            return n ^ (1 << i);
        }
        int next(int n, unordered_set<int> s) {
            int ans = 0;
            for (int i = 0; i < 32; ++i) {
                ans = toggle(n, i);
                if (s.find(ans) == s.end()) break;
            }
            return ans;
        }
    public:
        vector<int> grayCode(int n) {
            unordered_set<int> s{0};
            vector<int> ans(pow(2, n), 0);
            for (int i = 1; i < ans.size(); ++i) {
                s.insert(ans[i] = next(ans[i - 1], s));
            }
            return ans;
        }
    };
    
  • class Solution:
        def grayCode(self, n: int) -> List[int]:
            return [i ^ (i >> 1) for i in range(1 << n)]
    
    ############
    
    class Solution(object):
      def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n < 1:
          return [0]
        ans = [0] * (2 ** n)
        ans[1] = 1
        mask = 0x01
        i = 1
        while i < n:
          mask <<= 1
          for j in range(0, 2 ** i):
            root = (2 ** i)
            ans[root + j] = ans[root - j - 1] | mask
          i += 1
        return ans
    
    
  • func grayCode(n int) (ans []int) {
    	for i := 0; i < 1<<n; i++ {
    		ans = append(ans, i^(i>>1))
    	}
    	return
    }
    
  • /**
     * @param {number} n
     * @return {number[]}
     */
    var grayCode = function (n) {
        const ans = [];
        for (let i = 0; i < 1 << n; ++i) {
            ans.push(i ^ (i >> 1));
        }
        return ans;
    };
    
    

All Problems

All Solutions