#include <stdio.h>
#include <stdlib.h>

#define INT_BITS 32

typedef struct TrieNode {
    struct TrieNode* bit[2];
} TrieNode;

TrieNode* newTrieNode() {
	TrieNode* newNode = (TrieNode*)malloc(sizeof(TrieNode));
    if (newNode != NULL) {
        newNode->bit[0] = newNode->bit[1] = NULL;
    }
    return newNode;
}

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

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

void freeTrie(TrieNode* root) {
    if (root != NULL) {
        freeTrie(root->bit[0]);
        freeTrie(root->bit[1]);
        free(root);
    }
}

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

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