Using a Trie... (accepted)
Reference: LeetCode\nDifficulty: Medium\n\n## Problem\n\n> Given a non-empty array of numbers, a0, a1, a2, \u2026 , an-1, where 0 \u2264 ai < 2^31.\n\n> Find th
Reference: [LeetCode](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)\nDifficulty: <span class="orange">Medium</span>\n\n## Problem\n\n> Given a non-empty array of numbers, `a0, a1, a2, \u2026 , an-1`, where `0 \u2264 ai < 2^31`.\n\n> Find the maximum result of `ai` XOR `aj`, where `0 \u2264 i`, `j < n`.\n\n**Example:** \n\n```java\nInput: [3, 10, 5, 25, 2, 8]\nOutput: 28\nExplanation: The maximum result is 5 ^ 25 = 28.\n\nInput: [8,10,2]\nOutput: 10\n```\n\n**Follow up:** Could you do this in `O(n)` runtime?\n\n\n## Analysis\n\n### Brute-Force\n\n```java\npublic int findMaximumXOR(int[] nums) {\n  int n = nums.length;\n  if (n == 1) return 0;\n  int maxVal = Integer.MIN_VALUE;\n  for (int i = 0; i < n - 1; ++i) {\n    for (int j = i + 1; j < n; ++j) {\n      maxVal = Math.max(maxVal, nums[i] ^ nums[j]);\n    }\n  }\n  return maxVal;\n}\n```\n\n**Time:** `O(N^2)`\n**Space:** `O(1)`\n\n\n\n### Use Trie\n\nReference: [LeetCode Solution](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/)\n\n![](https://bloggg-1254259681.cos.na-siliconvalley.myqcloud.com/5dhef.jpg)\n\nA good practice for using tries to solve problems. It took me a long time to write the code... but still learned some handy string manipulations too.\n\n```java\n// trie\nstatic final int R = 2;\nclass TrieNode {\n  TrieNode[] next;\n  TrieNode() {\n    next = new TrieNode[R];\n  }\n}\n\npublic int findMaximumXOR(int[] nums) {\n  if (nums.length <= 1) return 0;\n  int maxNum = getMax(nums);\n  // 1000 8  log2(8)  = 3 --> 4\n  // 1001 9  log2(9)  > 3 --> 4  ---> (int) log2(num) + 1 (equivalent to Math.floor)\n  // 1111 15 log2(15) > 3 --> 4\n  int maxLen = (int)(Math.log(maxNum) / Math.log(2)) + 1;\n  String[] numsArr = getStringArray(nums, maxLen);\n  TrieNode root = generateTrie(numsArr);\n  return findTheOtherInTrie(root, nums, numsArr);\n}\n\nprivate int getMax(int[] nums) {\n  if (nums.length == 0) throw new IllegalArgumentException();\n  int maxVal = nums[0];\n  for (int val : nums) {\n    maxVal = Math.max(maxVal, val);\n  }\n  return maxVal;\n}\n\nprivate String[] getStringArray(int[] nums, int maxLen) {\n  int n = nums.length;\n  String[] result = new String[n];\n  String format = "%" + maxLen + "s";\n  for (int i = 0; i < n; ++i) {\n    result[i] = getBinaryString(nums[i], format); \n  }\n  return result;\n}\n\nprivate String getBinaryString(int num, String format) {\n  // or use toString(?, 2)\n  return String.format(format, Integer.toBinaryString(num)).replace(\' \', \'0\'); \n}\n\nprivate TrieNode generateTrie(String[] numsArr) {\n  TrieNode root = new TrieNode();\n  for (String s : numsArr) { // for each string\n    TrieNode p = root; // p must be here!!!!\n    for (int i = 0; i < s.length(); ++i) {  // for each char\n      int num = s.charAt(i) == \'0\' ? 0 : 1;\n      if (p.next[num] == null) {\n        p.next[num] = new TrieNode();\n      }\n      p = p.next[num];\n    }\n  }\n  return root;\n}\n\nprivate int findTheOtherInTrie(TrieNode root, int[] nums, String[] numsArr) {\n  int n = nums.length;\n  int maxXOR = Integer.MIN_VALUE;\n  for (int i = 0; i < n; ++i) {\n    String s = numsArr[i];\n    StringBuilder sb = new StringBuilder();\n    TrieNode maxP = root;\n    TrieNode otherP = root;\n    for (int j = 0; j < s.length(); ++j) {\n      int num = s.charAt(j) == \'0\' ? 0 : 1;\n      maxP = maxP.next[num];\n      // try to go to the opposite if possible\n      int direction = otherP.next[num ^ 1] != null ? (num ^ 1) : num;\n      sb.append(direction);\n      otherP = otherP.next[direction];\n    }\n    int otherNum = Integer.parseInt(sb.toString(), 2); // convert binary string to integer\n    maxXOR = Math.max(maxXOR, nums[i] ^ otherNum);\n  }\n  return maxXOR;\n}\n```\n\n**Time:** `O(N)`\n**Space:** `O(1)`
['Trie', 'Java']