Maximum Strong Pair XOR II
HardUpdated: Aug 2, 2025
Practice on:
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 _themaximum _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.
Examples
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 = [500,520,2500,3000]
Output: 1020
Explanation: There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.
Constraints
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 220 - 1
Solution
Method 1 – Trie with Sliding Window
Intuition
To maximize the XOR for strong pairs efficiently, sort the array and use a sliding window to maintain the valid range for each number. For each number, use a trie to quickly find the number in the window that gives the maximum XOR.
Approach
- Sort
nums. - For each
xinnums, maintain a window of numbersysuch that|x - y| <= min(x, y)(which, after sorting, isy >= x - yandy <= x + y). - Use a trie to insert numbers in the window and query for the maximum XOR with
x. - Slide the window as you iterate, removing numbers that are no longer valid.
- Return the maximum XOR found.
Code
C++
struct TrieNode {
TrieNode* child[2] = {};
};
class Solution {
public:
int maximumStrongPairXor(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), ans = 0, l = 0;
TrieNode* root = new TrieNode();
auto insert = [&](int x) {
TrieNode* node = root;
for (int i = 16; i >= 0; --i) {
int b = (x >> i) & 1;
if (!node->child[b]) node->child[b] = new TrieNode();
node = node->child[b];
}
};
auto query = [&](int x) {
TrieNode* node = root;
int res = 0;
for (int i = 16; i >= 0; --i) {
int b = (x >> i) & 1;
if (node->child[!b]) {
res |= (1 << i);
node = node->child[!b];
} else node = node->child[b];
}
return res;
};
for (int r = 0; r < n; ++r) {
while (l < r && nums[r] - nums[l] > nums[l]) ++l;
TrieNode* tmp = new TrieNode();
for (int i = l; i < r; ++i) insert(nums[i]);
if (r > l) ans = max(ans, query(nums[r]));
}
return ans;
}
};
Go
import "sort"
type Trie struct{child [2]*Trie}
func (t *Trie) Insert(x int) {
node := t
for i := 16; i >= 0; i-- {
b := (x >> i) & 1
if node.child[b] == nil {
node.child[b] = &Trie{}
}
node = node.child[b]
}
}
func (t *Trie) Query(x int) int {
node := t; res := 0
for i := 16; i >= 0; i-- {
b := (x >> i) & 1
if node.child[1-b] != nil {
res |= 1 << i
node = node.child[1-b]
} else {
node = node.child[b]
}
}
return res
}
func maximumStrongPairXor(nums []int) int {
sort.Ints(nums)
n, ans, l := len(nums), 0, 0
for r := 0; r < n; r++ {
for l < r && nums[r]-nums[l] > nums[l] { l++ }
trie := &Trie{}
for i := l; i < r; i++ { trie.Insert(nums[i]) }
if r > l { ans = max(ans, trie.Query(nums[r])) }
}
return ans
}
func max(a, b int) int { if a > b { return a }; return b }
Java
import java.util.*;
class Trie {
Trie[] child = new Trie[2];
}
class Solution {
public int maximumStrongPairXor(int[] nums) {
Arrays.sort(nums);
int n = nums.length, ans = 0, l = 0;
for (int r = 0; r < n; ++r) {
while (l < r && nums[r] - nums[l] > nums[l]) ++l;
Trie root = new Trie();
for (int i = l; i < r; ++i) insert(root, nums[i]);
if (r > l) ans = Math.max(ans, query(root, nums[r]));
}
return ans;
}
void insert(Trie root, int x) {
Trie node = root;
for (int i = 16; i >= 0; --i) {
int b = (x >> i) & 1;
if (node.child[b] == null) node.child[b] = new Trie();
node = node.child[b];
}
}
int query(Trie root, int x) {
Trie node = root; int res = 0;
for (int i = 16; i >= 0; --i) {
int b = (x >> i) & 1;
if (node.child[1-b] != null) {
res |= 1 << i;
node = node.child[1-b];
} else node = node.child[b];
}
return res;
}
}
Kotlin
class Trie { val child = arrayOfNulls<Trie>(2) }
class Solution {
fun maximumStrongPairXor(nums: IntArray): Int {
nums.sort()
var ans = 0; var l = 0
for (r in nums.indices) {
while (l < r && nums[r] - nums[l] > nums[l]) l++
val root = Trie()
for (i in l until r) insert(root, nums[i])
if (r > l) ans = maxOf(ans, query(root, nums[r]))
}
return ans
}
fun insert(root: Trie, x: Int) {
var node = root
for (i in 16 downTo 0) {
val b = (x shr i) and 1
if (node.child[b] == null) node.child[b] = Trie()
node = node.child[b]!!
}
}
fun query(root: Trie, x: Int): Int {
var node = root; var res = 0
for (i in 16 downTo 0) {
val b = (x shr i) and 1
if (node.child[1-b] != null) {
res = res or (1 shl i)
node = node.child[1-b]!!
} else node = node.child[b]!!
}
return res
}
}
Python
class Trie:
def __init__(self):
self.child = [None, None]
class Solution:
def maximumStrongPairXor(self, nums: list[int]) -> int:
nums.sort()
ans, l = 0, 0
for r, x in enumerate(nums):
while l < r and x - nums[l] > nums[l]:
l += 1
root = Trie()
for i in range(l, r):
node = root
for b in range(16, -1, -1):
bit = (nums[i] >> b) & 1
if not node.child[bit]:
node.child[bit] = Trie()
node = node.child[bit]
if r > l:
node = root
res = 0
for b in range(16, -1, -1):
bit = (x >> b) & 1
if node.child[1-bit]:
res |= 1 << b
node = node.child[1-bit]
else:
node = node.child[bit]
ans = max(ans, res)
return ans
Rust
struct Trie { child: [Option<Box<Trie>>; 2] }
impl Trie { fn new() -> Self { Trie { child: [None, None] } } }
impl Solution {
pub fn maximum_strong_pair_xor(nums: Vec<i32>) -> i32 {
let mut nums = nums;
nums.sort();
let mut ans = 0;
let mut l = 0;
for r in 0..nums.len() {
while l < r && nums[r] - nums[l] > nums[l] { l += 1; }
let mut root = Trie::new();
for i in l..r {
let mut node = &mut root;
for b in (0..=16).rev() {
let bit = (nums[i] >> b) & 1;
node = node.child[bit as usize].get_or_insert_with(|| Box::new(Trie::new()));
}
}
if r > l {
let mut node = &root;
let mut res = 0;
for b in (0..=16).rev() {
let bit = (nums[r] >> b) & 1;
if let Some(ref next) = node.child[1-bit as usize] {
res |= 1 << b;
node = next;
} else if let Some(ref next) = node.child[bit as usize] {
node = next;
}
}
ans = ans.max(res);
}
}
ans
}
}
TypeScript
class Trie { child: [Trie?, Trie?] = [undefined, undefined]; }
class Solution {
maximumStrongPairXor(nums: number[]): number {
nums.sort((a, b) => a - b);
let ans = 0, l = 0;
for (let r = 0; r < nums.length; ++r) {
while (l < r && nums[r] - nums[l] > nums[l]) ++l;
const root = new Trie();
for (let i = l; i < r; ++i) {
let node = root;
for (let b = 16; b >= 0; --b) {
const bit = (nums[i] >> b) & 1;
if (!node.child[bit]) node.child[bit] = new Trie();
node = node.child[bit]!;
}
}
if (r > l) {
let node = root, res = 0;
for (let b = 16; b >= 0; --b) {
const bit = (nums[r] >> b) & 1;
if (node.child[1-bit]) {
res |= 1 << b;
node = node.child[1-bit]!;
} else {
node = node.child[bit]!;
}
}
ans = Math.max(ans, res);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2 log M), wherenis the length ofnumsandMis the max value innums. For each number, we may build a trie of up tonnumbers, each with up to log M bits. - 🧺 Space complexity:
O(n log M), for the trie at each step.