Problem 421 from leetcode, O(n) solution using Trie

lc_421.cpp

class Solution {
public:
    struct Node {
        Node(): left(nullptr), right(nullptr) {}
        shared_ptr<Node> left, right;
    };

    typedef shared_ptr<Node> NodePtr;
    shared_ptr<Node> root;

    void add(int v) {
        NodePtr n = root;
        for (int i = 31; i >= 0; --i) {
            if ( ((v>>i)&1) == 1 ) {
                if (n->right == nullptr)
                    n->right.reset(new Node);
                n = n->right;
            } else {
                if (n->left == nullptr)
                    n->left.reset(new Node);
                n = n->left;
            }
        }
    }
    
    int findDifferent(int v) {
        int res = 0;
        NodePtr n = root;
        for (int i = 31; i >= 0; --i) {
            if ( ((v>>i)&1) == 1 ) {
                if ( n->left != nullptr ) {
                    n = n->left;
                } else {
                    n = n->right;
                    res |= 1 << i;
                }
            } else {
                if ( n->right != nullptr ) {
                    n = n->right;
                    res |= 1 << i;
                } else {
                    n = n->left;
                }
            }
        }
        return res;
    }

    int findMaximumXOR(vector<int>& nums) {
        root.reset(new Node);
        for (int v : nums) {
            add(v);
        }
        
        int maxsofar = 0;
        for (int v : nums) {
            maxsofar = max(maxsofar, v^findDifferent(v));
        }
        return maxsofar;
    }
};