Title: Gray Code Source: leetcode.com
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
|
1 2 3 4 |
00 - 0 01 - 1 11 - 3 10 - 2 |
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
Java 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
/* https://leetcode.com/problems/gray-code/ */ import java.util.List; import java.util.ArrayList; import java.util.Arrays; class GrayCode { public static void main(String args[]) { GrayCode gc = new GrayCode(); gc.grayCodeEfficient(10); } public List<Integer> grayCodeEfficient(int n) { List<Integer> list = new ArrayList<>(); for(int i=0;i<(int)Math.pow(2, n);i++) { list.add((i >> 1) ^ i); } System.out.println(list); return list; } // ---- Not Efficient ---- public List<Integer> grayCode(int n) { boolean[] added = new boolean[(int)Math.pow(2, n)]; Arrays.fill(added, false); List<Integer> list = new ArrayList<>(); list.add(0); added[0] = true; helper(list, added); System.out.println(list); return list; } public boolean helper(List<Integer> list, boolean[] added) { boolean check = true; for(int i=0;i<added.length;i++) { check = check & added[i]; } if(check) return true; for(int i=1;i<added.length;i++) { if(isSafe(i, list, added)) { added[i] = true; list.add(i); if(helper(list, added)) return true; added[i] = false; list.remove(list.size()-1); } } return false; } public boolean isSafe(int numToBeAdded, List<Integer> list, boolean[] added) { if(added[numToBeAdded]==true) return false; int a = list.get(list.size()-1); int b = numToBeAdded ^ a; int count = 0; while(b!=0) { count = count + (b&1); b = b>>>1; } if(count!=1) return false; return true; } } |