We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Strong Pair XOR I

Number: 3193

Difficulty: Easy

Paid? No

Companies: Amazon, ZScaler

Problem Description

Given a 0-indexed integer array nums, select two integers from the array such that they form a strong pair. A pair (x, y) is defined as strong if |x - y| <= min(x, y). The goal is to find the maximum possible bitwise XOR value among all strong pairs. Note that you are allowed to choose the same integer twice to form a pair.

Key Insights

  • A pair (x, y) is strong if the absolute difference between x and y does not exceed the smaller of the two numbers.
  • Self pairs, where both numbers are the same, always satisfy the condition (since 0 <= x).
  • Given the small constraints (nums.length <= 50), brute force checking of all pairs is efficient.
  • The XOR operation is straightforward and any valid pair’s XOR can be computed directly.
  • Brute force solution involves iterating over all possible pairs and updating a maximum value when conditions are met.

Space and Time Complexity

Time Complexity: O(n²), where n is the number of elements in nums, due to the nested iteration over pairs. Space Complexity: O(1), as no extra space apart from a few variables is used.

Solution

The problem can be solved by checking every possible pair in the array. For every pair (x, y), we verify that the strong pair condition |x - y| <= min(x, y) holds. If it does, we compute the XOR of x and y and update our maximum result if this XOR is greater than the current maximum. This exhaustive search is feasible given the small input size.

Code Solutions

# Function to calculate maximum strong pair XOR in Python
def maxStrongPairXor(nums):
    max_xor = 0
    n = len(nums)
    # Iterate over every possible pair (including self pairs)
    for i in range(n):
        for j in range(n):
            x = nums[i]
            y = nums[j]
            # Check the strong pair condition: |x - y| <= min(x, y)
            if abs(x - y) <= min(x, y):
                xor_val = x ^ y  # Compute bitwise XOR
                if xor_val > max_xor:
                    max_xor = xor_val  # Update maximum XOR value
    return max_xor

# Example usage
print(maxStrongPairXor([1,2,3,4,5]))  # Expected output: 7
← Back to All Questions