Maximum Strong Pair XOR I — Easy Problem & Solution

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 <= 50
• 1 <= nums[i] <= 100

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

1. Loop over every ordered pair (i, j), including i == j.
2. Keep the pair when |nums[i] - nums[j]| <= min(nums[i], nums[j]).
3. 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| <= x rather 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Number of Bit Changes to Make Two Integers Equal Easy
• Find the XOR of Numbers Which Appear Twice Easy
• Binary Watch Easy
• Smallest Number With All Set Bits Easy
• Shortest Subarray With OR at Least K I Easy
• Complement of Base 10 Integer Easy