Trie

class BitTrie {

 BitTrie left = null;

 BitTrie right = null;

 }

 public boolean containsDuplicate(int[] nums) {

 BitTrie root = new BitTrie();

 for(int num: nums) {

 BitTrie cur = root;

 for(int i = 31; i >= 0; i --) {

 if(((num >>> i) & 1) == 1) {

 if(cur.left == null) {

 cur.left = new BitTrie();

 }

 cur = cur.left;

 }else {

 if(cur.right == null) {

 cur.right = new BitTrie();

 }

 cur = cur.right;

 }

 }

 }



 int max = 0;

 for(int num: nums) {

 BitTrie cur = root;

 int i = 31, curNum = num;

 for(; i >= 0; i --) {

 if(((curNum >>> i) & 1) == 1) {

 if(cur.right != null) {

 cur = cur.right;

 curNum |= (1 << i);

 }else {

 cur = cur.left;

 }

 }else {

 if(cur.left != null) {

 cur = cur.left;

 curNum |= (1 << i);

 }else {

 cur = cur.right;

 }

 }

 max = Math.max(curNum, max);

 }

 }

 System.out.println(max);

 return true;

 }