Maximum Strong Pair XOR I
EasyPrompt
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:
numsExample 2:
numsExample 3:
nums
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
max_xorto 0. - Get the length of the array,
n. - Use a nested loop to iterate through all possible pairs of indices
(i, j)from0ton-1. - For each pair of numbers
x = nums[i]andy = nums[j], check if they form a strong pair using the conditionMath.abs(x - y) <= Math.min(x, y). - If the condition is met, calculate their bitwise XOR
x ^ y. - Update
max_xorwith the maximum value found so far:max_xor = Math.max(max_xor, x ^ y). - After iterating through all pairs, return
max_xor.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.