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

• Java
• C++
• Python
• Go
• Javascript

• 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