Maximum Strong Pair XOR I

Easy
721.

Maximum Strong Pair XOR I

Maximum Strong Pair XOR I is an easy coding problem on arrays, bit manipulation and trie, asked in Amazon, Adobe and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumStrongPairXor = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Maximum Strong Pair XOR I

  1. Hint 1

    At these limits the double loop over all ordered pairs is entirely adequate.

  2. Hint 2

    Rewriting the condition as max(x, y) <= 2 * min(x, y) makes it easier to reason about.

  3. 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

  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

Java

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