#include <stdio.h>

#define INT_BITS 32
#define MAX_NODES 1024 

// Trie node structure
typedef struct TrieNode {
    struct TrieNode* bit[2];
} TrieNode;

TrieNode trieNodes[MAX_NODES]; 
int trieNodeCount = 0; 


TrieNode* newTrieNode() {
    if (trieNodeCount >= MAX_NODES) {
        printf("Exceeded maximum trie nodes\n");
        return NULL;
    }
    TrieNode* newNode = &trieNodes[trieNodeCount++];
    newNode->bit[0] = NULL;
    newNode->bit[1] = NULL;
    return newNode;
}


void insert(TrieNode* root, int number) {
    TrieNode* current = root;
    int i, bit;
    for (i = INT_BITS - 1; i >= 0; i--) {
        bit = (number >> i) & 1;
        if (!current->bit[bit]) {
            current->bit[bit] = newTrieNode();
            if (!current->bit[bit]) return; 
        }
        current = current->bit[bit];
    }
}


int findMaxXOR(TrieNode* root, int number) {
    TrieNode* current = root;
    int maxXOR = 0;
    int i, bit;
    for (i = INT_BITS - 1; i >= 0; i--) {
        bit = (number >> i) & 1;
        if (current->bit[1 - bit]) {
            maxXOR |= (1 << i);
            current = current->bit[1 - bit];
        } else {
            current = current->bit[bit];
        }
    }
    return maxXOR;
}


int getMaxXOR(int* arr, int size) {
    TrieNode* root = newTrieNode();
    if (!root) return 0; 
    int maxXOR = 0;
    int i, currentXOR;
    for (i = 0; i < size; i++) {
        insert(root, arr[i]);
        currentXOR = findMaxXOR(root, arr[i]);
        if (currentXOR > maxXOR) {
            maxXOR = currentXOR;
        }
    }
    return maxXOR;
}

void main() {
    int arr[10] = {3, 10, 5, 25, 2, 8};
    int size = 6;
    int result = getMaxXOR(arr, size);
    printf("Maximum XOR: %d\n", result);
}