#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


class Trie
{
    struct Node {
        Node *left  = nullptr;
        Node *right = nullptr;
    };

private:
    void remove_trie(Node* node) 
    {
        if (node == nullptr) return;

        remove_trie(node->left);
        remove_trie(node->right);

        delete node;
    }

public:
    Trie() : m_trie(new Node()) { }

    void insert(const std::string &binary)
    {
        auto trie = m_trie;

        for (auto b : binary) {
            if (b == '0') {                     // left
                if (trie->left == nullptr)      // create left
                    trie->left = new Node();
                trie = trie->left;              // go left
            } else {                            // right
                if (trie->right == nullptr)     // create right
                    trie->right = new Node();
                trie = trie->right;             // go right
            }
        }
    }

    void max_xor(const std::string &binary, std::string &xor_binary) 
    {
        auto trie = m_trie;

        xor_binary = "";

        for (auto b : binary) {
            if (b == '0') {                     
                if (trie->right != nullptr) {   // try right
                    xor_binary += '1';
                    trie = trie->right;
                } else {
                    xor_binary += '0';
                    trie = trie->left;
                }
            } else {      
                if (trie->left != nullptr) {    // try left
                    xor_binary += '1';
                    trie = trie->left;
                } else {
                    xor_binary += '0';
                    trie = trie->right;
                }
            }
        }
    }

    ~Trie()
    {
        remove_trie(m_trie);
    }

private:
    Node *m_trie;
};


int main(void)
{
    std::vector<std::string> nums = 
    { 
        "000", 
        "010", 
        "011", 
        "101", 
        "110", 
        "111" 
    };

    std::string max_xor = "000";
    std::string bin_xor;

    auto trie = new Trie();

    for (auto num : nums) {
        trie->insert(num);
        trie->max_xor(num, bin_xor);

        auto value_max_xor = std::stoi(max_xor, nullptr, 2);
        auto value_bin_xor = std::stoi(bin_xor, nullptr, 2);

        if (value_max_xor < value_bin_xor)
            max_xor = bin_xor;
    }

    std::cout << max_xor << std::endl;

    delete trie;

    return 0;
}