#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;
}