Maximum XOR of Two Numbers in an Array

Problem

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Solution Approach

Expected Time complexity: $O(nlogn)$

Click - to see solution code

C++

typedef long long ll;
ll ans = 0;
class Node {
   public:
    ll data;
    unordered_map<ll, Node*> children;
    bool terminal;

    Node(ll d) {
        data = d;
        terminal = false;
    }
};
class Trie {
    Node* root;
    ll cnt;

   public:
    Trie() {
        root = new Node(0);
        cnt = 0;
    }

    void insert(ll w) {
        Node* temp = root;
        ll a = w;
        for (ll i = 30; i >= 0; i--) {
            ll bit = 1LL << i;
            bit &= w;
            ll aa = bit >> i;
            if (temp->children.count(aa)) {
                temp = temp->children[aa];
            } else {
                Node* n = new Node(aa);
                temp->children[aa] = n;
                temp = n;
            }
        }
        temp->terminal = true;
    }

    void find(ll w) {
        Node* temp = root;
        ll ans1 = 0;
        for (ll i = 30; i >= 0; i--) {
            ll bit = 1LL << i;
            bit &= w;
            ll aa = bit >> i;
            aa ^= 1LL;
            if (temp->children.count(aa)) {
                ans1 += 1LL << i;
                temp = temp->children[aa];
            } else {
                temp = temp->children[aa ^ 1];
            }
        }
        ans = max(ans, ans1);
        insert(w);
    }
};

class Solution {
   public:
    int findMaximumXOR(vector<int>& nums) {
        Trie t;
        ll n = nums.size();
        if (n == 1) {
            return 0;
        }
        ans = 0;
        t.insert(nums[0]);
        for (int i = 1; i < n; i++) {
            t.find(nums[i]);
        }
        return (int)ans;
    }
};