2932. Maximum Strong Pair XOR I

EasyBit ManipulationTrieArrayHash TableSliding Window

Problem Description

You are provided with an array nums which contains integers. The task is to find two integers from this array that satisfy a specific condition defined as being a strong pair. The condition for a strong pair is that the absolute difference between x and y must be less than or equal to the smaller of the two numbers (|x - y| <= min(x, y)). The goal is to choose a pair that not only meets this condition but also has the highest possible bitwise XOR value compared to all other strong pairs that could be formed from the array elements. It's also worth noting that you can use the same integer from the array twice to create a pair. The output of the problem is the maximum XOR value obtained from all valid strong pairs in the array.

Intuition

The intuition behind the given solution is to employ a brute-force approach to solve the problem. Since the problem does not impose a strong restriction on the size of the input array, we can afford to use a double loop to enumerate all possible pairs of numbers from the array. For each pair (x, y), we check if it meets the strong pair condition (|x - y| <= min(x, y)). If it does, we calculate the XOR of x and y (using the bitwise XOR operator ^) and keep track of the maximum XOR value obtained. By the end of the iteration over all pairs, we will have the maximum XOR value for all strong pairs in the array.

In summary, the solution approach arrives by considering the following points:

A brute-force method can be used without significant concern for performance unless the input size is very large.
Checking the strong pair condition and calculating the XOR are both constant-time operations.
Keeping track of the maximum XOR value seen so far while iterating over pairs ensures we have the correct answer by the end of the iterations.

Learn more about Trie and Sliding Window patterns.

Solution Approach

The solution uses a straightforward enumeration algorithm to check every possible pair in the given integer array nums. This approach does not require any special data structures or advanced algorithms, relying on the Python list given as input and couple of nested loops to generate pairs.

Here’s a step-by-step breakdown of the implementation:

A double for loop is constructed, where the first loop iterates over each element x in the array nums, and the second loop iterates over each element y in the array as well. This setup allows us to consider every possible pair (x, y) from nums.
For each pair (x, y), we evaluate the condition |x - y| <= min(x, y). To do this, we use Python's abs() function to find the absolute difference between x and y, and min(x, y) to find the smaller of the two numbers.
If the condition is satisfied, meaning the pair (x, y) is a strong pair, we calculate the bitwise XOR of x and y by using the ^ operator.
We employ Python's list comprehension combined with the max() function to iterate over all possible pairs, calculate their XOR values, and keep the maximum of these values. The max() function is called with a generator expression that yields the XOR of x and y for each strong pair.

The code snippet provided by the Solution class method, maximumStrongPairXor(self, nums: List[int]) -> int, returns the single highest XOR value discovered during the enumeration process.

The overall complexity of this approach is O(n^2), where n is the length of the array nums, since the enumeration involves checking each possible pair within the array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the array nums = [3, 10, 5, 25, 2, 8].

Initialize a variable named max_xor that will store the maximum XOR value found. Initially, this can be set to a very low value, such as zero.
Start with the first element in nums, which is 3. We then check it against every other element including itself:
- Check 3 with 3: They are the same, so |3 - 3| = 0 which is less than min(3, 3). The XOR is 3 ^ 3 = 0. max_xor remains 0.
- Check 3 with 10: The difference |3 - 10| = 7 which is not less than min(3, 10) = 3. This pair is not strong, so we move on.
- Check 3 with 5: The difference |3 - 5| = 2 which is less than min(3, 5) = 3. The XOR is 3 ^ 5 = 6. max_xor is updated to 6.
- Check 3 with 25, 2, and 8 the same way, updating max_xor if we find a higher XOR from a strong pair.
Move to the next element in nums, 10, and repeat the process for each pair:
- Check 10 with itself and then 5, 25, 2, 8. If we find any strong pairs, we evaluate the XOR and check if it's higher than max_xor and update accordingly.
For example, when checking against 5, since |10 - 5| = 5 is equal to min(10, 5) = 5, the pair (10, 5) is considered strong. The XOR of 10 and 5 is 10 ^ 5 = 15, which is higher than the current max_xor of 6, so max_xor is updated to 15.
Continue through all the elements of nums, comparing each with every other element, checking the strong pair condition, and keeping the maximum XOR value found.

At the end of the process, max_xor will hold the highest XOR value possible from all strong pairs. In this example, the maximum XOR value is found to be 28, which is the XOR of the pair (5, 25) where |5 - 25| = 20 is less than min(5, 25) = 5.

Thus, the maximumStrongPairXor function would return 28 for the input array [3, 10, 5, 25, 2, 8].

Solution Implementation

1from typing import List  # We import List from typing to annotate the type of the nums parameter.
2
3class Solution:
4    def maximum_strong_pair_xor(self, nums: List[int]) -> int:
5        # Initialize variable to store the maximum XOR value found.
6        max_xor = 0
7      
8        # Iterate over each possible pair in the list.
9        for i in range(len(nums)):
10            for j in range(len(nums)):
11                # Calculate the absolute difference between the two numbers.
12                difference = abs(nums[i] - nums[j])
13              
14                # Calculate the minimum of the two numbers.
15                minimum = min(nums[i], nums[j])
16
17                # Check if the difference between the two numbers 
18                # is less than or equal to the minimum of the two.
19                if difference <= minimum:
20                    # Calculate XOR of the current pair and update the max_xor
21                    # if it's greater than the current maximum.
22                    possible_max_xor = nums[i] ^ nums[j]
23                    max_xor = max(max_xor, possible_max_xor)
24      
25        # Return the maximum XOR value found among all the valid pairs.
26        return max_xor
27

1class Solution {
2    public int maximumStrongPairXor(int[] nums) {
3        // Initialize the variable to store the maximum XOR value found. 
4        // It is set to zero since XOR of any number with 0 is the number itself, 
5        // and we're trying to find the maximum of all XOR operations.
6        int maxPairXor = 0;
7      
8        // Traverse all possible pairs in the array
9        for (int i = 0; i < nums.length; i++) {      // Iterate through each element in nums with index i
10            for (int j = 0; j < nums.length; j++) {  // Iterate through each element in nums with index j
11                // Check the condition that the absolute difference between the two numbers 
12                // should be less than or equal to the smaller of the two numbers.
13                if (Math.abs(nums[i] - nums[j]) <= Math.min(nums[i], nums[j])) {
14                    // If the condition is met, calculate the XOR of the current pair
15                    int currentXor = nums[i] ^ nums[j];
16                    // Update the maximum XOR value if the current XOR is greater than the current maximum
17                    maxPairXor = Math.max(maxPairXor, currentXor);
18                }
19            }
20        }
21      
22        // Return the maximum XOR value found
23        return maxPairXor;
24    }
25}
26

1#include <vector>
2#include <algorithm> // for std::max
3
4class Solution {
5public:
6    // Defines a function that calculates the maximum XOR value of any strong pair in the array.
7    // A strong pair is defined as a pair of numbers (x, y) where abs(x - y) is less than or 
8    // equal to the minimum of x and y.
9    int maximumStrongPairXor(std::vector<int>& nums) {
10        int max_xor = 0; // Initialize the maximum XOR value to zero.
11      
12        // Iterate through all possible pairs of numbers within the nums array.
13        for (int x : nums) {
14            for (int y : nums) {
15                // Check if x and y form a strong pair as per the given condition.
16                if (abs(x - y) <= std::min(x, y)) {
17                    // Update max_xor to hold the maximum value between the current max_xor 
18                    // and the XOR of x and y.
19                    max_xor = std::max(max_xor, x ^ y);
20                }
21            }
22        }
23      
24        // Return the calculated maximum XOR value.
25        return max_xor;
26    }
27};
28

1/**
2 * Computes the maximum XOR value of a strong pair from the array.
3 * A strong pair (x, y) satisfies the condition: abs(x - y) <= min(x, y).
4 * @param {number[]} nums - The array of numbers to evaluate.
5 * @return {number} The maximum XOR value of any strong pair in the array.
6 */
7function maximumStrongPairXor(nums: number[]): number {
8    let maximumXor = 0; // Holds the maximum XOR value found.
9
10    // Iterate through each number in the array.
11    for (const num1 of nums) {
12        // Iterate through each number in the array to find all possible pairs.
13        for (const num2 of nums) {
14            // Check if the current pair (num1, num2) is a strong pair.
15            if (Math.abs(num1 - num2) <= Math.min(num1, num2)) {
16                // Update maximumXor if XOR of the current pair is greater than the current maximumXor.
17                maximumXor = Math.max(maximumXor, num1 ^ num2);
18            }
19        }
20    }
21  
22    // Return the maximum XOR value found among all strong pairs.
23    return maximumXor;
24}
25

Time and Space Complexity

The time complexity of the provided code is O(n^2) where n is the length of the input array nums. This quadratic time complexity arises because there are two nested loops, with each element in nums being paired with every other element.

For every element x in nums, the code iterates through the entire nums array again to find another element y, and then it calculates x ^ y if the condition abs(x - y) <= min(x, y) is satisfied. There are n choices for x and for each x, there are n choices for y, resulting in n * n pairs to check, thus the O(n^2) complexity.

The space complexity of the provided code is O(1). This constant space complexity is because the algorithm only uses a fixed amount of additional space that does not depend on the input size. All operations are performed in place and the max function keeps track of the current maximum without requiring additional space proportional to the size of the input nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know