Maximum Strong Pair XOR I — Solution in Python, Java & C++
Maximum Strong Pair XOR I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Strong Pair XOR I is an easy coding problem on arrays, bit manipulation and trie, asked in Amazon, Adobe and Zoho interviews.
- Difficulty: Easy
- Topics: Arrays, Bit Manipulation, Trie
- Asked at: Amazon, Adobe, Zoho
- 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 (x, y) is a strong pair when |x - y| <= min(x, y). The two elements may be the same element of nums picked twice.
Return the maximum XOR over all strong pairs of values drawn from nums.
Example 1
Input: nums = [1,2,3,4,5]
Output: 7
Explanation: (3, 4) is strong because |3 - 4| = 1 is at most 3, and 3 XOR 4 = 7.
Example 2
Input: nums = [10,100]
Output: 0
Explanation: The only strong pairs are an element with itself, and x XOR x is 0.
Example 3
Input: nums = [5,6,25,30]
Output: 7
Explanation: (25, 30) gives 7 and is strong since |25 - 30| = 5 is at most 25.
Constraints
1 <= nums.length <= 501 <= nums[i] <= 100
Hints for Maximum Strong Pair XOR I
Hint 1
At these limits the double loop over all ordered pairs is entirely adequate.
Hint 2
Rewriting the condition as
max(x, y) <= 2 * min(x, y)makes it easier to reason about.Hint 3
The scalable version sorts the values and sweeps a window, feeding a binary trie.
How to solve Maximum Strong Pair XOR I
Check every pair directly. The strong-pair test is a single comparison, and the XOR of a qualifying pair is a candidate answer.
Approach
- Loop over every ordered pair
(i, j), includingi == j. - Keep the pair when
|nums[i] - nums[j]| <= min(nums[i], nums[j]). - Track the maximum XOR seen.
Why it works
Allowing i == j guarantees the answer is at least 0, and checking every pair is exhaustive. The condition is equivalent to max <= 2 · min, which is why sorting turns it into a sliding window in the harder version of this problem.
Complexity
- Time —
O(n²) - Space —
O(1)
Pitfalls
- Forgetting that an element may pair with itself makes the answer undefined when no other pair is strong.
- Testing
|x - y| <= xrather than against the minimum accepts pairs that are not strong.
Reference solution
Python
from typing import List
def maximumStrongPairXor(nums: List[int]) -> int:
best = 0
for a in nums:
for b in nums:
if abs(a - b) <= min(a, b):
best = max(best, a ^ b)
return bestJava
public static int maximumStrongPairXor(int[] nums) {
int best = 0;
for (int a : nums) {
for (int b : nums) {
if (Math.abs(a - b) <= Math.min(a, b)) best = Math.max(best, a ^ b);
}
}
return best;
}C++
int maximumStrongPairXor(vector<int>& nums) {
int best = 0;
for (int a : nums) {
for (int b : nums) {
if (abs(a - b) <= min(a, b)) best = max(best, a ^ b);
}
}
return best;
}JavaScript
var maximumStrongPairXor = function(nums) {
var best = 0;
for (var i = 0; i < nums.length; i++) {
for (var j = 0; j < nums.length; j++) {
var a = nums[i], b = nums[j];
if (Math.abs(a - b) <= Math.min(a, b)) {
var x = a ^ b;
if (x > best) best = x;
}
}
}
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