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)$


Comment