# 421. Maximum XOR of Two Numbers in an Array

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:

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

## Analysis

### Brute-Force

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.

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

Comment
Junhao Wang
a software engineering cat