Maximum Strong Pair XOR I

• Initialize a variable max_xor to 0.
• Get the length of the array, n.
• Use a nested loop to iterate through all possible pairs of indices (i, j) from 0 to n-1.
• For each pair of numbers x = nums[i] and y = nums[j], check if they form a strong pair using the condition Math.abs(x - y) <= Math.min(x, y).
• If the condition is met, calculate their bitwise XOR x ^ y.
• Update max_xor with the maximum value found so far: max_xor = Math.max(max_xor, x ^ y).
• After iterating through all pairs, return max_xor.

The core idea is to use nested loops to generate all pairs (nums[i], nums[j]). The strong pair condition is |x - y| <= min(x, y), which we can check directly for each pair. A variable max_xor is initialized to 0. The outer loop iterates from i = 0 to n-1, and the inner loop also iterates from j = 0 to n-1, where n is the length of the array. This ensures we check all pairs, including a number with itself. Inside the inner loop, for the pair (x, y) = (nums[i], nums[j]), we check if Math.abs(x - y) <= Math.min(x, y). If the condition is true, we compute x ^ y and update max_xor = Math.max(max_xor, x ^ y). After checking all pairs, max_xor will hold the final result.

1class Solution {2    public int maximumStrongPairXor(int[] nums) {3        int max_xor = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            for (int j = 0; j < n; j++) {7                int x = nums[i];8                int y = nums[j];9                if (Math.abs(x - y) <= Math.min(x, y)) {10                    max_xor = Math.max(max_xor, x ^ y);11                }12            }13        }14        return max_xor;15    }16}

• First, simplify the strong pair condition. For x <= y, |x - y| <= min(x, y) becomes y - x <= x, which is y <= 2*x.
• Sort the input array nums in non-decreasing order.
• Initialize max_xor = 0, a left pointer to 0, and a Trie data structure.
• Iterate through the sorted array with a right pointer (or a for-each loop). Let the current element be y.
• Insert y into the Trie.
• The Trie now contains numbers from a window. We need to shrink this window from the left to ensure all numbers x in the Trie satisfy the strong pair condition with y. The condition is x >= y / 2. So, while nums[left] * 2 < y, remove nums[left] from the Trie and increment left.
• Now, all numbers remaining in the Trie form a strong pair with y. Query the Trie to find the number x that maximizes x ^ y.
• Update the global max_xor with the result from the query.
• After iterating through all numbers, return max_xor.

The key insight is to rephrase the strong pair condition and process the numbers in a sorted order. After sorting nums, for any pair (x, y) with x <= y, the condition is y <= 2*x. We can iterate through each number y in the sorted array and, for each y, find the best partner x that satisfies x <= y and y <= 2*x.

A Trie combined with a sliding window is perfect for this. We iterate through nums with a right pointer (let y = nums[right]). We maintain a window of candidates nums[left...right] in a Trie. As we advance right, we add y to the Trie. Then, we shrink the window from the left by removing nums[left] from the Trie as long as it's too small to be a partner for y (i.e., nums[right] > 2 * nums[left]). After this, every number x in the Trie is a valid partner for y. We can then query the Trie to find the x that maximizes x ^ y in O(K) time, where K is the number of bits. We repeat this for all y and find the overall maximum XOR.

1class Solution {2    class TrieNode {3        TrieNode[] children = new TrieNode[2];4        int count = 0;5    }6 7    class Trie {8        private TrieNode root = new TrieNode();9        // For nums <= 100, we need at most 7 bits (2^7=128)10        private static final int MAX_BIT = 7;11 12        public void insert(int num) {13            TrieNode curr = root;14            for (int i = MAX_BIT; i >= 0; i--) {15                int bit = (num >> i) & 1;16                if (curr.children[bit] == null) {17                    curr.children[bit] = new TrieNode();18                }19                curr = curr.children[bit];20                curr.count++;21            }22        }23 24        public void remove(int num) {25            TrieNode curr = root;26            for (int i = MAX_BIT; i >= 0; i--) {27                int bit = (num >> i) & 1;28                // It's guaranteed that the node exists when remove is called29                curr = curr.children[bit];30                curr.count--;31            }32        }33 34        public int findMaxXor(int num) {35            TrieNode curr = root;36            int maxXor = 0;37            for (int i = MAX_BIT; i >= 0; i--) {38                int bit = (num >> i) & 1;39                int toggleBit = bit ^ 1;40                if (curr.children[toggleBit] != null && curr.children[toggleBit].count > 0) {41                    maxXor |= (1 << i);42                    curr = curr.children[toggleBit];43                } else {44                    curr = curr.children[bit];45                }46            }47            return maxXor;48        }49    }50 51    public int maximumStrongPairXor(int[] nums) {52        Arrays.sort(nums);53        int n = nums.length;54        Trie trie = new Trie();55        int left = 0;56        int max_xor = 0;57 58        for (int y : nums) {59            trie.insert(y);60            while (nums[left] * 2 < y) {61                trie.remove(nums[left]);62                left++;63            }64            max_xor = Math.max(max_xor, trie.findMaxXor(y));65        }66        return max_xor;67    }68}