# Java 42ms solution using a trie and recursion

• I have this rather straightforward solution that finishes in 42 ms. Once or twice it gave me a time limit exception though. I'm not sure about complexity, as sometimes when the bit patterns are 1 0 and 0 1 I explore both branches. Any comment on the complexity analysis is very much appreciated. Here is the code:

``````public class MaximumXORTwoNumbersArray {

public static int findMaximumXOR(int[] nums) {
Node node = buildTrie(nums);
return find(node, node, 30, 0);
}

static int find(Node p, Node q, int count, int max) {
if (count < 0) return max;

if (p.hasLeft() && p.hasRight() && q.hasLeft() && q.hasRight())
return Math.max(find(p.left, q.right, count - 1, max | (1 << count)),
find(p.right, q.left, count - 1, max | (1 << count)));

if (p.hasLeft() && q.hasRight())
return find(p.left, q.right, count - 1, max | (1 << count));

if (p.hasRight() && q.hasLeft())
return find(p.right, q.left, count - 1, max | (1 << count));

if (p.hasRight() && q.hasRight())
return find(p.right, q.right, count - 1, max);

return find(p.left, q.left, count - 1, max);
}

static Node buildTrie(int[] nums) {
Node root = new Node();
int mask = 1 << 30;
for (int i : nums)
return root;
}

static Node insert(int i, int mask, Node node) {
if (node == null) node = new Node();
if (mask == 0) { node.val = i; return node; }
if ((i & mask) != 0) // current bit is one
node.right = insert(i, mask >> 1, node.right);
else
node.left  = insert(i, mask >> 1, node.left);
return node;
}

static class Node {
Node left;
Node right;
int val;

boolean isLeaf() { return left == null && right == null; }
boolean hasLeft() { return left != null; }
boolean hasRight() {return right != null; }
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.