Maximum Strong Pair XOR II — Solution in Python, Java & C++
Maximum Strong Pair XOR II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Strong Pair XOR II is a hard coding problem on arrays, bit manipulation and sliding window, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Bit Manipulation, Sliding Window, Trie
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A pair of integers x and y is strong when |x - y| <= min(x, y).
Given an array nums of positive integers, choose two of its integers (you may pick the same element twice) that form a strong pair, so that their bitwise XOR is as large as possible.
Return that maximum XOR value.
Example 1
Input: nums = [6,9,12]
Output: 15
Explanation: (6, 9) is strong since 3 <= 6, and `6 XOR 9 = 15`. (6, 12) and (9, 12) are strong too but give 10 and 5.
Example 2
Input: nums = [3,50]
Output: 0
Explanation: (3, 50) is not strong, so only (3, 3) and (50, 50) remain, both with XOR 0.
Example 3
Input: nums = [7,4,5]
Output: 3
Constraints
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 2^20 - 1
Hints for Maximum Strong Pair XOR II
Hint 1
With
x <= y, the strong condition simplifies toy <= 2x.Hint 2
Sort the numbers. For each
ytaken as the larger element, the valid partnersxform a contiguous window ending atywhose left edge only moves right.Hint 3
Keep the window in a binary trie that supports deletion (a count per node) and query the maximum XOR with
ygreedily from the top bit.
How to solve Maximum Strong Pair XOR II
After sorting, the partners of each y are exactly the values in [y/2, y], a sliding window. A binary trie with per-node counts can add and remove numbers and answer "maximum XOR with y" in O(20).
Approach
- Sort
numsascending and set a left pointer to 0. - For each
yin order: insertyinto the trie (incrementing counts along its path). - While
2 * nums[left] < y, removenums[left]from the trie (decrementing counts) and advanceleft. - Walk the trie from bit 19 down, preferring the child with the opposite bit of
ywhenever its count is positive; the bits gained form the best XOR for thisy. - Return the largest XOR seen.
Why it works
For x <= y, |x - y| <= min(x, y) reads y - x <= x, i.e. 2x >= y. Since the array is sorted and y only grows, the smallest allowed x only grows too, so the window moves monotonically and contains exactly the allowed partners when the query runs. The greedy walk maximises XOR because a higher bit outweighs all lower bits together; the count check ensures the walk follows only numbers still inside the window.
Complexity
- Time —
O(n log n + n · 20) - Space —
O(n · 20)
Pitfalls
- Deleting must decrement counts, not unlink nodes, because other numbers can share the path.
- The pair (y, y) is always strong, so the answer is at least 0 and the trie is never empty during a query.
- Compare
2 * x < y(strict) to evict —y = 2xis still strong.
Reference solution
Python
from typing import List
def maximumStrongPairXor(nums: List[int]) -> int:
srt = sorted(nums)
n = len(srt)
ch = [0] * ((n * 20 + 2) * 2)
cnt = [0] * (n * 20 + 2)
nodes = 1
def update(v, d):
nonlocal nodes
node = 0
for b in range(19, -1, -1):
bit = (v >> b) & 1
if not ch[node * 2 + bit]:
ch[node * 2 + bit] = nodes
nodes += 1
node = ch[node * 2 + bit]
cnt[node] += d
best = 0
left = 0
for y in srt:
update(y, 1)
while srt[left] * 2 < y:
update(srt[left], -1)
left += 1
node = 0
cur = 0
for b in range(19, -1, -1):
want = ((y >> b) & 1) ^ 1
c = ch[node * 2 + want]
if c and cnt[c] > 0:
cur |= 1 << b
node = c
else:
node = ch[node * 2 + (want ^ 1)]
if cur > best:
best = cur
return bestJava
public static int maximumStrongPairXor(int[] nums) {
int[] srt = nums.clone();
Arrays.sort(srt);
int n = srt.length;
int[] ch = new int[(n * 20 + 2) * 2];
int[] cnt = new int[n * 20 + 2];
int[] nodes = {1};
int best = 0, left = 0;
for (int i = 0; i < n; i++) {
int y = srt[i];
mspxUpdate(ch, cnt, nodes, y, 1);
while (srt[left] * 2 < y) { mspxUpdate(ch, cnt, nodes, srt[left], -1); left++; }
int node = 0, cur = 0;
for (int b = 19; b >= 0; b--) {
int want = ((y >> b) & 1) ^ 1;
int c = ch[node * 2 + want];
if (c != 0 && cnt[c] > 0) { cur |= 1 << b; node = c; }
else node = ch[node * 2 + (want ^ 1)];
}
best = Math.max(best, cur);
}
return best;
}
static void mspxUpdate(int[] ch, int[] cnt, int[] nodes, int v, int d) {
int node = 0;
for (int b = 19; b >= 0; b--) {
int bit = (v >> b) & 1;
if (ch[node * 2 + bit] == 0) ch[node * 2 + bit] = nodes[0]++;
node = ch[node * 2 + bit];
cnt[node] += d;
}
}C++
int maximumStrongPairXor(vector<int>& nums) {
vector<int> srt(nums);
sort(srt.begin(), srt.end());
int n = srt.size();
vector<int> ch((n * 20 + 2) * 2, 0), cnt(n * 20 + 2, 0);
int nodes = 1;
auto update = [&](int v, int d) {
int node = 0;
for (int b = 19; b >= 0; b--) {
int bit = (v >> b) & 1;
if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
node = ch[node * 2 + bit];
cnt[node] += d;
}
};
int best = 0, left = 0;
for (int i = 0; i < n; i++) {
int y = srt[i];
update(y, 1);
while (srt[left] * 2 < y) { update(srt[left], -1); left++; }
int node = 0, cur = 0;
for (int b = 19; b >= 0; b--) {
int want = ((y >> b) & 1) ^ 1;
int c = ch[node * 2 + want];
if (c && cnt[c] > 0) { cur |= 1 << b; node = c; }
else node = ch[node * 2 + (want ^ 1)];
}
best = max(best, cur);
}
return best;
}JavaScript
var maximumStrongPairXor = function(nums) {
var srt = nums.slice().sort(function(a, b) { return a - b; });
var n = srt.length;
var ch = new Int32Array((n * 20 + 2) * 2), cnt = new Int32Array(n * 20 + 2);
var nodes = 1;
function update(v, d) {
var node = 0;
for (var b = 19; b >= 0; b--) {
var bit = (v >> b) & 1;
if (!ch[node * 2 + bit]) ch[node * 2 + bit] = nodes++;
node = ch[node * 2 + bit];
cnt[node] += d;
}
}
var best = 0, left = 0;
for (var i = 0; i < n; i++) {
var y = srt[i];
update(y, 1);
while (srt[left] * 2 < y) { update(srt[left], -1); left++; }
var node = 0, cur = 0;
for (var b = 19; b >= 0; b--) {
var want = ((y >> b) & 1) ^ 1;
var c = ch[node * 2 + want];
if (c && cnt[c] > 0) { cur |= 1 << b; node = c; }
else node = ch[node * 2 + (want ^ 1)];
}
if (cur > best) best = cur;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation