## Saturday, October 15, 2016

### LeetCode 421 - Maximum XOR of Two Numbers in an Array

https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].
Could you do this in O(n) runtime?

Input: [3, 10, 5, 25, 2, 8]
Output: 28

```递归函数定义为：solve(nums0, nums1, mask)。

http://www.cnblogs.com/grandyang/p/5991530.html

http://blog.csdn.net/mebiuw/article/details/52901057

a^b = c ->a^c=b,b^c=a
// a^b = c ->a^c=b,b^c=a public int findMaximumXOR(int[] nums) { int max = 0, mask = 0; for(int i = 31; i >= 0; i--){ //mask从0x01 ->0x03等一直变化，取后i位 mask = mask | (1 << i); Set<Integer> set = new HashSet<>(); for(int num : nums){ set.add(num & mask); } //tmp表示当前的最大 int tmp = max | (1 << i); System.out.println(mask+" "+tmp+" "+max); for(int prefix : set){ //证明存在一个数使得tmp^x = prefix if(set.contains(tmp ^ prefix)) { max = tmp; break; } } } return max; }
https://segmentfault.com/a/1190000007283296

``````    public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
// test each bit pose, 判断能不能构成所需要的值；
for(int i = 31; i >= 0; i --) {
Set<Integer> set = new HashSet<>();
for(int num : nums) {
}
// 假设当前所能达到的最大值是这个temp值；
int tmp = max | (1 << i);
for(Integer prefix : set) {
if(set.contains(prefix ^ tmp)) {
// 如果能组成就直接break
max = tmp;
break;
}
}
}
return max;
}``````
http://hankerzheng.com/blog/LeetCode-Maximum-XOR-of-Two-Numbers-in-an-Array

X.

https://discuss.leetcode.com/topic/63299/python-6-lines-bit-by-bit/2
Build the answer bit by bit from left to right. Let's say we already know the largest first seven bits we can create. How to find the largest first eight bits we can create? Well it's that maximal seven-bits prefix followed by 0 or 1. Append 0 and then try to create the 1 one (i.e., `answer ^ 1`) from two eight-bits prefixes from `nums`. If we can, then change that 0 to 1.
``````    int findMaximumXOR(vector<int>& nums) {
int res = 0;
unordered_set<int> pre;
for (int i = 31; i >= 0; i--) {
res <<= 1;
pre.clear();
for (auto n : nums)
pre.insert(n >> i);
for (auto p : pre)
if (pre.find((res ^ 1) ^ p) != pre.end()) {
res++;
break;
}
}
return res;
}``````
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
example: Given [14, 11, 7, 2], which in binary are [1110, 1011, 0111, 0010].
Since the MSB is 3, I'll start from i = 3 to make it simplify.
1. i = 3, set = {1000, 0000}, max = 1000
2. i = 2, set = {1100, 1000, 0100, 0000}, max = 1100
3. i = 1, set = {1110, 1010, 0110, 0010}, max = 1100
4. i = 0, set = {1110, 1011, 0111, 0010}, max = 1100
The mask is 1000, 1100, 1110, 1111.
``````    public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for (int i = 31; i >= 0; i--) {
HashSet<Integer> set = new HashSet<Integer>();
for (int num : nums) {
}

/* Use 0 to keep the bit, 1 to find XOR
* 0 ^ 0 = 0
* 0 ^ 1 = 1
* 1 ^ 0 = 1
* 1 ^ 1 = 0
*/
int tmp = max | (1 << i); // in each iteration, there are pair(s) whoes Left bits can XOR to max
for (int prefix : set) {
if (set.contains(tmp ^ prefix)) {
max = tmp;
}
}
}
return max;
}``````
I saw deeply and found out a very important xor feature I missed, that is: if a^b=c, then a^c=b, b^c=a. That's why the answer using this code:
``````            for(int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
``````
Agreed. Actually, this is the most important operation that made this code linear. Instead of choosing 2 from n, we verify if we can achieve maximum value -- 1 -- on each bit reversely based on the feature you have mentioned
to iteratively determine what would be each bit of the final result from left to right. And it narrows down the candidate group iteration by iteration. e.g. assume input are a,b,c,d,...z, 26 integers in total. In first iteration, if you found that a, d, e, h, u differs on the MSB(most significant bit), so you are sure your final result's MSB is set. Now in second iteration, you try to see if among a, d, e, h, u there are at least two numbers make the 2nd MSB differs, if yes, then definitely, the 2nd MSB will be set in the final result. And maybe at this point the candidate group shinks from a,d,e,h,u to a, e, h. Implicitly, every iteration, you are narrowing down the candidate group, but you don't need to track how the group is shrinking, you only cares about the final result.
``````    public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for(int i = 31; i >= 0; i--){
Set<Integer> set = new HashSet<>();
for(int num : nums){
}
int tmp = max | (1 << i);
for(int prefix : set){
if(set.contains(tmp ^ prefix)) {
max = tmp;
break;
}
}
}
return max;
}``````

https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
``````    class Trie {
Trie[] children;
public Trie() {
children = new Trie[2];
}
}

public int findMaximumXOR(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
// Init Trie.
Trie root = new Trie();
for(int num: nums) {
Trie curNode = root;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode.children[curBit] == null) {
curNode.children[curBit] = new Trie();
}
curNode = curNode.children[curBit];
}
}
int max = Integer.MIN_VALUE;
for(int num: nums) {
Trie curNode = root;
int curSum = 0;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode.children[curBit ^ 1] != null) {
curSum += (1 << i);
curNode = curNode.children[curBit ^ 1];
}else {
curNode = curNode.children[curBit];
}
}
max = Math.max(curSum, max);
}
return max;
}``````
It gets me TLE as well. Ditching the `Trie` class and just using `Object[]` gets it accepted in about 185 ms:
``````    public int findMaximumXOR(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
// Init Trie.
Object[] root = {null, null};
for(int num: nums) {
Object[] curNode = root;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode[curBit] == null) {
curNode[curBit] = new Object[]{null, null};
}
curNode = (Object[]) curNode[curBit];
}
}
int max = Integer.MIN_VALUE;
for(int num: nums) {
Object[] curNode = root;
int curSum = 0;
for(int i = 31; i >= 0; i --) {
int curBit = (num >>> i) & 1;
if(curNode[curBit ^ 1] != null) {
curSum += (1 << i);
curNode = (Object[]) curNode[curBit ^ 1];
}else {
curNode = (Object[]) curNode[curBit];
}
}
max = Math.max(curSum, max);
}
return max;
}``````
https://discuss.leetcode.com/topic/64753/31ms-o-n-java-solution-using-trie
We add the number into the trie and find the max possible XOR result at the same time.
Node.set() method will set the new node in the trie if needed and return the new node.
After setting the node, find the opposite bit in the trie to maximize the possible XOR result.
``````    public class Node {
Node one;
Node zero;
Node() {
this.one = null;
this.zero = null;
}
Node set(int n) {
if (n == 0) {
if (this.one == null) this.one = new Node();
return this.one;
}
if (this.zero == null) this.zero = new Node();
return this.zero;
}
}

public int findMaximumXOR(int[] nums) {
Node root = new Node();
int re = 0;
for (int num : nums) {
int digit = num;
int tmp = 0;
Node setNode = root;
Node findNode = root;
int pos = 30;
while (pos >= 0) {
digit = (num >> pos) & 1;
setNode = setNode.set(digit);
if (digit == 1) {
if (findNode.one != null) {
tmp = tmp | (1 << pos);
findNode = findNode.one;
} else {
findNode = findNode.zero;
}
} else {
if (findNode.zero != null) {
tmp = tmp | (1 << pos);
findNode = findNode.zero;
} else {
findNode = findNode.one;
}
}
pos--;
}
re = Math.max(re, tmp);
}
return re;
}``````

TODO
https://discuss.leetcode.com/topic/64431/a-solution-based-on-bartoszkp-s-with-missing-test-cases

http://www.geeksforgeeks.org/minimum-xor-value-pair/
Given an array of integers. Find the pair in an array which has minimum XOR value

`int` `minXOR(``int` `arr[], ``int` `n)`
`{`
`    ``int` `min_xor = INT_MAX; ``// Initialize result`
`    ``// Generate all pair of given array`
`    ``for` `(``int` `i=0; i < n; i++)`
`        ``for` `(``int` `j=i+1; j<n; j++)`
`            ``// update minimum xor value if required`
`            ``min_xor = min(min_xor, arr[i] ^ arr[j] );`
`    ``return` `min_xor;`
`}`

An Efficient solution can solve the above problem in O(n) time under the assumption that integers take fixed number of bits to store. The idea is to use Trie Data Structure. Below is algorithm.
```1). Create an empty trie. Every node of trie contains two children
for 0 and 1 bits.
2). Initialize min_xor = INT_MAX, insert arr[0] into trie
3). Traversal all array element one-by-one starting from second.
a. First find minimum setbet difference value in trie
do xor of current element with minimum setbit diff that value
b. update min_xor value if required
c. insert current array element in trie
4). return min_xor
```
`struct` `TrieNode`
`{`
`    ``int` `value; ``// used in leaf node`
`    ``TrieNode * Child[2];`
`};`
`// Utility function to create a new Trie node`
`TrieNode * getNode()`
`{`
`    ``TrieNode * newNode = ``new` `TrieNode;`
`    ``newNode->value = 0;`
`    ``newNode->Child[0] = newNode->Child[1] = NULL;`
`    ``return` `newNode;`
`}`
`// utility function insert new key in trie`
`void` `insert(TrieNode *root, ``int` `key)`
`{`
`    ``TrieNode *temp = root;`
`    ``// start from the most significant bit , insert all`
`    ``// bit of key one-by-one into trie`
`    ``for` `(``int` `i = INT_SIZE-1; i >= 0; i--)`
`    ``{`
`        ``// Find current bit in given prefix`
`        ``bool` `current_bit = (key & (1<<i));`
`        ``// Add a new Node into trie`
`        ``if` `(temp->Child[current_bit] == NULL)`
`            ``temp->Child[current_bit] = getNode();`
`        ``temp = temp->Child[current_bit];`
`    ``}`
`    ``// store value at leafNode`
`    ``temp->value = key ;`
`}`
`// Returns minimum XOR value of an integer inserted`
`// in Trie and given key.`
`int`  `minXORUtil(TrieNode * root, ``int` `key)`
`{`
`    ``TrieNode * temp = root;`
`    ``for` `(``int` `i=INT_SIZE-1; i >= 0; i--)`
`    ``{`
`        ``// Find current bit in given prefix`
`        ``bool` `current_bit = ( key & ( 1<<i) );`
`        ``// Traversal Trie, look for prefix that has`
`        ``// same bit`
`        ``if` `(temp->Child[current_bit] != NULL)`
`            ``temp = temp->Child[current_bit];`
`        ``// if there is no same bit.then looking for`
`        ``// opposite bit`
`        ``else` `if``(temp->Child[1-current_bit] !=NULL)`
`            ``temp = temp->Child[1-current_bit];`
`    ``}`
`    ``// return xor value of minimum bit difference value`
`    ``// so we get minimum xor value`
`    ``return` `key ^ temp->value;`
`}`
`// Returns minimum xor value of pair in arr[0..n-1]`
`int` `minXOR(``int` `arr[], ``int` `n)`
`{`
`    ``int` `min_xor = INT_MAX;  ``// Initialize result`
`    ``// create a True and insert first element in it`
`    ``TrieNode *root = getNode();`
`    ``insert(root, arr[0]);`
`    ``// Traversr all array elementd and find minimum xor`
`    ``// for every element`
`    ``for` `(``int` `i = 1 ; i < n; i++)`
`    ``{`
`        ``// Find minimum XOR value of current element with`
`        ``// previous elements inserted in Trie`
`        ``min_xor = min(min_xor, minXORUtil(root, arr[i]));`
`        ``// insert current array value into Trie`
`        ``insert(root, arr[i]);`
`    ``}`
`    ``return` `min_xor;`
`}`