# Maximum Strong Pair XOR I
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-strong-pair-xor-i)
Canonical: https://scaleengineer.com/dsa/problems/maximum-strong-pair-xor-i
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table, Trie
**Companies:** [ZScaler](https://scaleengineer.com/companies/zscaler)
---
## Problem
You are given a **0-indexed** integer array `nums`. A pair of integers `x` and `y` is called a **strong** pair if it satisfies the condition:

* `|x - y| <= min(x, y)`

You need to select two integers from `nums` such that they form a strong pair and their bitwise `XOR` is the **maximum** among all strong pairs in the array.

Return _the **maximum**_ `XOR` _value out of all possible strong pairs in the array_ `nums`.

**Note** that you can pick the same integer twice to form a pair.

**Example 1:**

**Input:** nums = [1,2,3,4,5]
**Output:** 7
**Explanation:** There are 11 strong pairs in the array `nums`: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.

**Example 2:**

**Input:** nums = [10,100]
**Output:** 0
**Explanation:** There are 2 strong pairs in the array `nums`: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.

**Example 3:**

**Input:** nums = [5,6,25,30]
**Output:** 7
**Explanation:** There are 6 strong pairs in the array `nums`: (5, 5), (5, 6), (6, 6), (25, 25), (25, 30) and (30, 30).
The maximum XOR possible from these pairs is 25 XOR 30 = 7 since the only other non-zero XOR value is 5 XOR 6 = 3.

**Constraints:**

* `1 <= nums.length <= 50`
* `1 <= nums[i] <= 100`

# Approaches
## Brute-Force Iteration
This approach involves checking every possible pair of numbers from the input array. For each pair, we verify if it meets the "strong pair" criteria. If it does, we calculate their bitwise XOR and update our maximum XOR value found so far. Given the small constraints of the problem (`N <= 50`), this straightforward method is sufficient and easy to implement.
**Time:** O(N^2), where N is the number of elements in `nums`. We have two nested loops, each running N times, leading to a quadratic runtime. · **Space:** O(1), as we only use a few variables to store the state, regardless of the input size.
**Pros:** Very simple to understand and implement.; Requires no extra space.; Fast enough for the given problem constraints.
**Cons:** The `O(N^2)` time complexity makes it inefficient for large input arrays.
### Explanation
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.

```java
class Solution {
    public int maximumStrongPairXor(int[] nums) {
        int max_xor = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int x = nums[i];
                int y = nums[j];
                if (Math.abs(x - y) <= Math.min(x, y)) {
                    max_xor = Math.max(max_xor, x ^ y);
                }
            }
        }
        return max_xor;
    }
}
```
### Algorithm
- 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`.

## Optimized Approach with Trie and Sliding Window
This approach improves upon the brute-force method by using a more advanced data structure, a Trie (Prefix Tree), combined with a sliding window technique. First, we sort the array. Then, for each number `y`, we efficiently find the best partner `x` from a valid range of candidates using the Trie. The strong pair condition `|x - y| <= min(x, y)` simplifies to `y <= 2*x` when `x <= y`. The sliding window, managed by two pointers, maintains a set of candidate `x` values in the Trie that can form a strong pair with the current `y`, allowing for an efficient search for the maximum XOR.
**Time:** O(N log N + N * K), where N is the length of `nums` and K is the number of bits in the maximum number (a small constant). The `O(N log N)` is for sorting. The main loop runs N times, and inside, Trie operations and the amortized cost of the while loop result in `O(N * K)` work. The total time is dominated by sorting. · **Space:** O(N * K), where N is the number of elements and K is the number of bits in the maximum number. The Trie can store up to N numbers, each creating a path of length K.
**Pros:** Asymptotically more efficient than the brute-force approach.; Scales well to larger input sizes where a brute-force solution would be too slow.
**Cons:** Significantly more complex to implement due to the Trie data structure and its associated methods (`insert`, `remove`, `findMaxXor`).; The constant factor overhead from sorting and Trie operations might make it slightly slower than brute-force for very small N.
### Explanation
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.

```java
class Solution {
    class TrieNode {
        TrieNode[] children = new TrieNode[2];
        int count = 0;
    }

    class Trie {
        private TrieNode root = new TrieNode();
        // For nums <= 100, we need at most 7 bits (2^7=128)
        private static final int MAX_BIT = 7;

        public void insert(int num) {
            TrieNode curr = root;
            for (int i = MAX_BIT; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (curr.children[bit] == null) {
                    curr.children[bit] = new TrieNode();
                }
                curr = curr.children[bit];
                curr.count++;
            }
        }

        public void remove(int num) {
            TrieNode curr = root;
            for (int i = MAX_BIT; i >= 0; i--) {
                int bit = (num >> i) & 1;
                // It's guaranteed that the node exists when remove is called
                curr = curr.children[bit];
                curr.count--;
            }
        }

        public int findMaxXor(int num) {
            TrieNode curr = root;
            int maxXor = 0;
            for (int i = MAX_BIT; i >= 0; i--) {
                int bit = (num >> i) & 1;
                int toggleBit = bit ^ 1;
                if (curr.children[toggleBit] != null && curr.children[toggleBit].count > 0) {
                    maxXor |= (1 << i);
                    curr = curr.children[toggleBit];
                } else {
                    curr = curr.children[bit];
                }
            }
            return maxXor;
        }
    }

    public int maximumStrongPairXor(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        Trie trie = new Trie();
        int left = 0;
        int max_xor = 0;

        for (int y : nums) {
            trie.insert(y);
            while (nums[left] * 2 < y) {
                trie.remove(nums[left]);
                left++;
            }
            max_xor = Math.max(max_xor, trie.findMaxXor(y));
        }
        return max_xor;
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

```java
class Solution {
public
  int maximumStrongPairXor(int[] nums) {
    int ans = 0;
    for (int x : nums) {
      for (int y : nums) {
        if (Math.abs(x - y) <= Math.min(x, y)) {
          ans = Math.max(ans, x ^ y);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumStrongPairXor(vector<int> &nums) {
    int ans = 0;
    for (int x : nums) {
      for (int y : nums) {
        if (abs(x - y) <= min(x, y)) {
          ans = max(ans, x ^ y);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int: return max(
        x ^ y for x in nums for y in nums if abs(x - y) <= min(x, y))

```