//
// Created by 罗炳国 on 2023/7/19.
//

#ifndef PFJ_CODE08_FINDMAXIMUMXOR_H
#define PFJ_CODE08_FINDMAXIMUMXOR_H

#include "commonHeader.h"

/**
 * 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
 * https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
 * */

struct node {
    node() {
        for (int i = 0; i < 2; i++)
            next[i] = nullptr;
    }
    struct node *next[2];
};

class numTrie {
public:
    void add(int num) {
        node *cur = &head;
        for (int off = 31; off >= 0; off--) {
            // 取出第off位的path
            int path = (num >> off) & 1;
            cur->next[path] = cur->next[path] == nullptr ? new node : cur->next[path];
            cur = cur->next[path];
        }
    }

    int maxXor(int num) {
        node *cur = &head;
        int ans = 0;
        for (int off = 31; off >= 0; off--) {
            int path = (num >> off) & 1;
            // 期待最优路径
            int best = off == 31 ? path : (path ^ 1);
            // 实际遇到的
            best = cur->next[best] == nullptr ? (best ^ 1) : best;
            ans |= (best ^ path) << off;
            cur = cur->next[best];
        }
        return ans;
    }

private:
    node head;
};

class code08_findMaximumXOR {
public:
    int findMaximumXOR(vector<int>& nums) {
        int ans = INT32_MIN, N = nums.size();
        if (N < 2) return 0;
        numTrie trie;
        trie.add(nums[0]);
        for (int i = 1; i < N; i++) {
            ans = max(ans, trie.maxXor(nums[i]));
            trie.add(nums[i]);
        }
        return ans;
    }

};

#endif //PFJ_CODE08_FINDMAXIMUMXOR_H