Maximum Strong Pair XOR I #2 Most Asked

Easy

2 views

Topics:

ArraysTwo PointersBit Manipulation

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:

Input: nums = [1,2,3,4,5]
Output: 7
Explanation: There are 11 strong pairs in the array nums: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.

Example 2:

Input: nums = [10,100]
Output: 0
Explanation: There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.

Example 3:

Input: nums = [5,6,25,30]
Output: 7
Explanation: There are 6 strong pairs in the array nums: (5, 5), (5, 6), (6, 6), (25, 25), (25, 30) and (30, 30).
The maximum XOR possible from these pairs is 25 XOR 30 = 7 since the only other non-zero XOR value is 5 XOR 6 = 3.

Constraints:

1 <= nums.length <= 50
1 <= nums[i] <= 100

Try coding it in LeetCode

Maximum Strong Pair XOR I #2 Most Asked

Easy

Zscaler

2 views

Topics:

ArraysTwo PointersBit Manipulation

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:

Input: nums = [1,2,3,4,5]
Output: 7
Explanation: There are 11 strong pairs in the array nums: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.

Example 2:

Input: nums = [10,100]
Output: 0
Explanation: There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.

Example 3:

Input: nums = [5,6,25,30]
Output: 7
Explanation: There are 6 strong pairs in the array nums: (5, 5), (5, 6), (6, 6), (25, 25), (25, 30) and (30, 30).
The maximum XOR possible from these pairs is 25 XOR 30 = 7 since the only other non-zero XOR value is 5 XOR 6 = 3.

Constraints:

1 <= nums.length <= 50
1 <= nums[i] <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the input array?
Can the input array be empty or null?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when determining the maximum XOR value?
If no strong pair exists, what value should I return?
By "strong pair", do you mean the absolute difference between nums[i] and nums[j] must be less than or equal to 1, or is there another definition of 'strong'?

Brute Force Solution

Approach

The brute force method for this problem involves checking every single possible pair of numbers from the given set. For each pair, we determine if it qualifies as a 'strong pair' based on a distance requirement and if so, calculate a score for the pair.

Here's how the algorithm would work step-by-step:

Consider the first number in the set.
Pair this first number with every other number in the set, including itself.
For each pair, check if the absolute difference between the two numbers is less than or equal to the smaller of the two numbers; if it is not, the pair is discarded, and we move on to the next pair.
If the pair meets the distance criteria, compute the score for the pair. The score is calculated by performing a bitwise exclusive OR (XOR) on the two numbers.
Keep track of the highest score encountered so far. Start with a score of zero.
Move on to the next number in the set and repeat the pairing and scoring process.
Continue doing this until every number has been paired with every other number and their scores have been evaluated.
The highest score you've kept track of is the answer.

Code Implementation

def maximum_strong_pair_xor_i(numbers):
    maximum_xor = 0

    # Iterate through each number
    for first_number in numbers:
        for second_number in numbers:

            # Check if the pair is a strong pair
            if abs(first_number - second_number) <= min(first_number, second_number):

                # Calculate XOR value
                current_xor = first_number ^ second_number

                #Update maximum_xor if necessary
                if current_xor > maximum_xor:
                    maximum_xor = current_xor

    return maximum_xor

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n numbers in the input array and, for each number, compares it with every other number in the array, including itself. This results in a nested loop structure where, for each of the n elements, we perform work proportional to n. Therefore, the total number of operations scales as approximately n * n, and the time complexity is O(n²).

Space Complexity

O(1) – The described algorithm iterates through pairs of numbers in the input but only uses a single variable to store the maximum XOR value encountered so far. It does not use any auxiliary data structures like lists, arrays, or hash maps to store intermediate results. Therefore, the amount of extra memory required remains constant regardless of the input size N, where N is the number of elements in the input set. The space complexity is thus O(1).

Optimal Solution

Approach

The key to efficiently finding the maximum XOR value of a strong pair is to consider pairs that are relatively close to each other in value. Instead of comparing every single pair, we focus on examining numbers that are likely to form a strong pair and potentially maximize the XOR result.

Here's how the algorithm would work step-by-step:

First, put the numbers in order from smallest to largest.
Then, go through the ordered numbers and, for each number, look at the numbers that are close to it in value.
Check if each pair of close numbers is a 'strong pair' (one number is no more than twice as big as the other).
If it's a strong pair, calculate their XOR value.
Keep track of the biggest XOR value you find during this process.
The biggest XOR value you found is your answer.

Code Implementation

def maximum_strong_pair_xor(numbers):
    numbers.sort()
    max_xor_value = 0

    for i in range(len(numbers)): 
        for j in range(i, len(numbers)): 
            # Only consider pairs where one number is at most twice the other.
            if numbers[i] <= 2 * numbers[j] and numbers[j] <= 2 * numbers[i]:

                current_xor_value = numbers[i] ^ numbers[j]
                # Track the largest XOR value encountered.
                max_xor_value = max(max_xor_value, current_xor_value)

    return max_xor_value

Big(O) Analysis

Time Complexity

O(n log n) – The initial step of sorting the input array nums of size n takes O(n log n) time. After sorting, we iterate through each number in the sorted array. For each number, we check elements that are close to it to identify strong pairs. While the number of nearby elements checked for each element is not fixed, within the outer loop the amount of close values to check would be a small constant. Given that the nested loop to find strong pairs runs in at most O(n) time in the worst case and since sorting dominates, the overall time complexity is O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in place, which does not require auxiliary space. The algorithm iterates through the sorted array and calculates XOR values, storing only the maximum XOR value found so far. Thus, it uses a constant amount of extra space regardless of the input size N, where N is the number of elements in the input array.

Edge Cases

Case	How to Handle
Empty array nums	Return 0 since no strong pair exists.
nums array with only one element	Return 0 since a pair requires two elements.
All numbers in nums are 0	Return 0, as 0 XOR 0 is 0, which is the maximum possible.
Large nums array with all identical values	Check if the first two elements form a valid pair; if so, their XOR value is the answer.
Large nums array where one number dominates and is much larger than others	Iterating through all possible pairs will find the best strong pair XOR.
nums array contains very large integers that could potentially cause integer overflow in XOR operation	XOR operation doesn't cause overflow, but the int data type must be sufficient for all possible XOR results; if the input numbers can result in numbers outside of Int, we should switch to using long.
nums array with duplicates	The definition of strong pair disallows the case of selecting the same index twice; our nested loops take care of it.
All possible pairs result in 0 XOR	The algorithm will return 0 in such cases because 0 is the initial value, so no special handling is required.

Empty array nums

How to Handle:

Return 0 since no strong pair exists.

nums array with only one element

How to Handle:

Return 0 since a pair requires two elements.

All numbers in nums are 0

How to Handle:

Return 0, as 0 XOR 0 is 0, which is the maximum possible.

Large nums array with all identical values

How to Handle:

Check if the first two elements form a valid pair; if so, their XOR value is the answer.

Large nums array where one number dominates and is much larger than others

How to Handle:

Iterating through all possible pairs will find the best strong pair XOR.

nums array contains very large integers that could potentially cause integer overflow in XOR operation

How to Handle:

XOR operation doesn't cause overflow, but the int data type must be sufficient for all possible XOR results; if the input numbers can result in numbers outside of Int, we should switch to using long.

nums array with duplicates

How to Handle:

The definition of strong pair disallows the case of selecting the same index twice; our nested loops take care of it.

All possible pairs result in 0 XOR

How to Handle:

The algorithm will return 0 in such cases because 0 is the initial value, so no special handling is required.