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

#define INT_BITS 32
#define MAX_NODES 1024 
#define MAX_ARRAY_SIZE 10
#define RAND_MAX_VALUE 100  // maximum random number value

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

TrieNode trieNodes[MAX_NODES]; 
int trieNodeCount = 0; 

// === Clear trie memory safely ===
void clearTrie()
{
    int i;
    for(i = 0; i < MAX_NODES; i++) {
        trieNodes[i].bit[0] = NULL;
        trieNodes[i].bit[1] = NULL;
    }
    trieNodeCount = 0;
}

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

// === Insert number into trie ===
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];
    }
}

// === Find max XOR for given number ===
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;
}

// === Compute max XOR from array & track best pair ===
int getMaxXOR(int* arr, int size, int* num1, int* num2) {
    clearTrie();  // ensure trie is empty before use

    TrieNode* root = newTrieNode();
    if (!root) return 0; 

    int maxXOR = 0;
    int i, currentXOR;

    *num1 = 0;
    *num2 = 0;

    for (i = 0; i < size; i++) {
        insert(root, arr[i]);
        currentXOR = findMaxXOR(root, arr[i]);
        if (currentXOR > maxXOR) {
            maxXOR = currentXOR;
            *num1 = arr[i];
            *num2 = arr[i] ^ maxXOR; // second number from XOR relation
        }
    }
    return maxXOR;
}

// === Zorro entry point ===
function run() {
    int size = MAX_ARRAY_SIZE;
    int arr[MAX_ARRAY_SIZE];
    int i;

    // Generate random integers
    printf("\nGenerated numbers: ");
    for (i = 0; i < size; i++) {
        arr[i] = random(RAND_MAX_VALUE); 
        printf("%d ", arr[i]);
    }
    printf("\n");

    int n1, n2;
    int result = getMaxXOR(arr, size, &n1, &n2);

    printf("Maximum XOR: %d (from %d ^ %d)\n", result, n1, n2);
}