1class Trie {
2    private Trie[] children = new Trie[2]; // Trie children to represent binary digits 0 and 1
3    private int count = 0; // Variable to keep track of the presence of numbers
4
5    public Trie() {
6        // Constructor for initialization
7    }
8
9    // Function to insert a number into the Trie
10    public void insert(int number) {
11        Trie node = this;
12        // Starting from the 20th bit moving towards the least significant bit
13        for (int i = 20; i >= 0; --i) {
14            int bit = (number >> i) & 1; // Extract the bit at the current position
15            // If there is no Trie node for this bit, create one
16            if (node.children[bit] == null) {
17                node.children[bit] = new Trie();
18            }
19            node = node.children[bit]; // Move to the child node representing the current bit
20            ++node.count; // Increment the count at the current Trie node
21        }
22    }
23
24    // Function to find the maximum XOR with the given number
25    public int search(int number) {
26        Trie node = this;
27        int maximumXor = 0; // Store the result for maximum XOR value
28        // Iterate over the bits of the number
29        for (int i = 20; i >= 0; --i) {
30            int bit = (number >> i) & 1; // Extract the bit at the current position
31            // Check if the complementary bit exists and has a positive count
32            if (node.children[bit ^ 1] != null && node.children[bit ^ 1].count > 0) {
33                maximumXor |= 1 << i; // Set the bit in the answer to 1
34                node = node.children[bit ^ 1]; // Move to the child node having the complementary bit
35            } else {
36                node = node.children[bit]; // Otherwise move to the child node having the same bit
37            }
38        }
39        return maximumXor; // Return the calculated maximum XOR value
40    }
41
42    // Function to remove a number from the Trie
43    public void remove(int number) {
44        Trie node = this;
45        // Iterate over the bits of the number to remove it from the Trie
46        for (int i = 20; i >= 0; --i) {
47            int bit = (number >> i) & 1; // Extract the bit at the current position
48            node = node.children[bit]; // Move to the child node representing the current bit
49            --node.count; // Decrement the count at the current node
50        }
51    }
52}
53
54class Solution {
55    // Method to find the maximum XOR pair from the given array such that the second number is not more than twice the first
56    public int maximumStrongPairXor(int[] nums) {
57        Arrays.sort(nums); // Sort the input array
58        Trie trie = new Trie(); // Initialize a Trie
59        int result = 0; // Variable to store the result
60        int i = 0; // Initialize the pointer for the sliding window
61        for (int number : nums) {
62            trie.insert(number); // Insert the number into the Trie
63            // If the current number is more than twice the smallest number in the current sliding window, remove the smallest number
64            while (number > nums[i] * 2) {
65                trie.remove(nums[i++]);
66            }
67            // Update the result with the maximum XOR found so far
68            result = Math.max(result, trie.search(number));
69        }
70        return result; // Return the maximum XOR value found
71    }
72}
73

1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Trie {
6public:
7    Trie* children[2]; // binary trie nodes for 0 and 1
8    int count; // count of numbers that have passed through this node 
9
10    Trie() : count(0) {
11        children[0] = nullptr;
12        children[1] = nullptr;
13    }
14
15    // Inserts an integer into the trie
16    void insert(int number) {
17        Trie* node = this;
18        for (int i = 20; i >= 0; --i) {
19            int bit = (number >> i) & 1; // extract the i-th bit of the number
20            if (node->children[bit] == nullptr) {
21                node->children[bit] = new Trie();
22            }
23            node = node->children[bit];
24            ++node->count; // increment the passage count
25        }
26    }
27
28    // Searches for the maximum XOR of an integer with the trie
29    int search(int number) {
30        Trie* node = this;
31        int max_xor = 0; // variable to store the maximum XOR value
32        for (int i = 20; i >= 0; --i) {
33            int bit = (number >> i) & 1;
34            // check if there is a complementary bit to maximize XOR
35            if (node->children[bit ^ 1] != nullptr && node->children[bit ^ 1]->count > 0) {
36                max_xor |= 1 << i; // update maximum XOR value
37                node = node->children[bit ^ 1]; // move to complementary bit if available
38            } else {
39                node = node->children[bit]; // else move to same bit
40            }
41        }
42        return max_xor; // return the maximum XOR found
43    }
44
45    // Removes an integer from the trie
46    void remove(int number) {
47        Trie* node = this;
48        for (int i = 20; i >= 0; --i) {
49            int bit = (number >> i) & 1;
50            node = node->children[bit];
51            --node->count; // decrement the passage count
52        }
53    }
54};
55
56class Solution {
57public:
58    // Finds the maximum XOR of two distinct elements in the array such that the second element is not greater than twice the first element
59    int maximumStrongPairXor(vector<int>& nums) {
60        sort(nums.begin(), nums.end()); // sort the input numbers
61        Trie* trie = new Trie();
62        int max_xor = 0; // variable to store the maximum XOR
63        int i = 0; // two pointers
64
65        for (int y : nums) {
66            trie->insert(y);
67            // keep removing elements while the condition (y > nums[i] * 2) is true
68            while (y > nums[i] * 2) {
69                trie->remove(nums[i++]);
70            }
71            max_xor = max(max_xor, trie->search(y)); // update maximum XOR value
72        }
73        return max_xor; // return the maximum XOR found among pairs
74    }
75};
76

1// Define the structure of a Trie node with children array and count.
2interface TrieNode {
3    children: (TrieNode | null)[];
4    count: number;
5}
6
7// Function to create a new Trie node initialized with children set to null and count set to 0.
8function createTrieNode(): TrieNode {
9    return { children: [null, null], count: 0 };
10}
11
12// Function to insert a number into the Trie.
13function insertIntoTrie(root: TrieNode, x: number): void {
14    let node = root;
15    for (let i = 20; i >= 0; i--) {
16        const bit = (x >> i) & 1;
17        if (node.children[bit] === null) {
18            node.children[bit] = createTrieNode();
19        }
20        node = node.children[bit]!;
21        node.count++;
22    }
23}
24
25// Function to search the Trie for the maximum XOR of a number with elements in the Trie.
26function searchTrie(root: TrieNode, x: number): number {
27    let node = root;
28    let maxXor = 0;
29    for (let i = 20; i >= 0; i--) {
30        const bit = (x >> i) & 1;
31        const oppositeBit = bit ^ 1;
32        if (node.children[oppositeBit] !== null && node.children[oppositeBit]!.count > 0) {
33            maxXor |= 1 << i;
34            node = node.children[oppositeBit]!;
35        } else {
36            node = node.children[bit]!;
37        }
38    }
39    return maxXor;
40}
41
42// Function to remove a number from the Trie.
43function removeFromTrie(root: TrieNode, x: number): void {
44    let node = root;
45    for (let i = 20; i >= 0; i--) {
46        const bit = (x >> i) & 1;
47        node = node.children[bit]!;
48        node.count--;
49    }
50}
51
52// Function to calculate the maximum XOR of a "strong pair" in an array.
53// A pair (i, j) is strong if i < j and nums[i] is at most twice as small as nums[j].
54function maximumStrongPairXor(nums: number[]): number {
55    // Sort the array in non-decreasing order.
56    nums.sort((a, b) => a - b);
57    const trieRoot = createTrieNode();
58    let maxPairXor = 0;
59    let leftIndex = 0;
60
61    for (const current of nums) {
62        insertIntoTrie(trieRoot, current);
63
64        // Ensure we only consider "strong pairs".
65        while (current > nums[leftIndex] * 2) {
66            removeFromTrie(trieRoot, nums[leftIndex]);
67            leftIndex++;
68        }
69
70        // Update the maximum XOR of a strong pair.
71        maxPairXor = Math.max(maxPairXor, searchTrie(trieRoot, current));
72    }
73
74    return maxPairXor;
75}
76