Reference: LeetCode
Difficulty: Medium

My Post: Using a Trie… (accepted)

Problem

Given a non-empty array of numbers, $a_0$, $a_1$, $a_2$, … , $a_{n-1}$, where $0$ ≤ $a_i$ < $2^{31}$.

Find the maximum result of $a_i$ XOR $a_j$, where 0 ≤ i, j < n.

Example: 

1
2
3
4
5
6
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

Input: [8,10,2]
Output: 10

Follow up: Could you do this in $O(n)$ runtime?

Analysis

Brute-Force

1
2
3
4
5
6
7
8
9
10
11
public int findMaximumXOR(int[] nums) {
  int n = nums.length;
  if (n == 1) return 0;
  int maxVal = Integer.MIN_VALUE;
  for (int i = 0; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
      maxVal = Math.max(maxVal, nums[i] ^ nums[j]);
    }
  }
  return maxVal;
}

Time: $O(N^2)$
Space: $O(1)$

Use Trie

Reference: LeetCode Solution

A 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.

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
81
// trie
static final int R = 2;
class TrieNode {
  TrieNode[] next;
  TrieNode() {
    next = new TrieNode[R];
  }
}

public int findMaximumXOR(int[] nums) {
  if (nums.length <= 1) return 0;
  int maxNum = getMax(nums);
  // 1000 8  log2(8)  = 3 --> 4
  // 1001 9  log2(9)  > 3 --> 4  ---> (int) log2(num) + 1 (equivalent to Math.floor)
  // 1111 15 log2(15) > 3 --> 4
  int maxLen = (int)(Math.log(maxNum) / Math.log(2)) + 1;
  String[] numsArr = getStringArray(nums, maxLen);
  TrieNode root = generateTrie(numsArr);
  return findTheOtherInTrie(root, nums, numsArr);
}

private int getMax(int[] nums) {
  if (nums.length == 0) throw new IllegalArgumentException();
  int maxVal = nums[0];
  for (int val : nums) {
    maxVal = Math.max(maxVal, val);
  }
  return maxVal;
}

private String[] getStringArray(int[] nums, int maxLen) {
  int n = nums.length;
  String[] result = new String[n];
  String format = "%" + maxLen + "s";
  for (int i = 0; i < n; ++i) {
    result[i] = getBinaryString(nums[i], format); 
  }
  return result;
}

private String getBinaryString(int num, String format) {
  // or use toString(?, 2)
  return String.format(format, Integer.toBinaryString(num)).replace(' ', '0'); 
}

private TrieNode generateTrie(String[] numsArr) {
  TrieNode root = new TrieNode();
  for (String s : numsArr) { // for each string
    TrieNode p = root; // p must be here!!!!
    for (int i = 0; i < s.length(); ++i) {  // for each char
      int num = s.charAt(i) == '0' ? 0 : 1;
      if (p.next[num] == null) {
        p.next[num] = new TrieNode();
      }
      p = p.next[num];
    }
  }
  return root;
}

private int findTheOtherInTrie(TrieNode root, int[] nums, String[] numsArr) {
  int n = nums.length;
  int maxXOR = Integer.MIN_VALUE;
  for (int i = 0; i < n; ++i) {
    String s = numsArr[i];
    StringBuilder sb = new StringBuilder();
    TrieNode maxP = root;
    TrieNode otherP = root;
    for (int j = 0; j < s.length(); ++j) {
      int num = s.charAt(j) == '0' ? 0 : 1;
      maxP = maxP.next[num];
      // try to go to the opposite if possible
      int direction = otherP.next[num ^ 1] != null ? (num ^ 1) : num;
      sb.append(direction);
      otherP = otherP.next[direction];
    }
    int otherNum = Integer.parseInt(sb.toString(), 2); // convert binary string to integer
    maxXOR = Math.max(maxXOR, nums[i] ^ otherNum);
  }
  return maxXOR;
}

Time: $O(N)$
Space: $O(1)$