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 = [500,520,2500,3000] Output: 1020 Explanation: There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000). The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 220 - 1When 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:
This double loop pairs every index with every index, including a value with itself. A pair is kept when the absolute difference is at most the smaller value. The answer is the largest exclusive-or among the pairs that pass.
Here's how the algorithm would work step-by-step:
def maximumStrongPairXor(numbers):
maximum_xor_so_far = 0
collection_size = len(numbers)
# We must check every number against every other number to find all possible pairs.
for first_index in range(collection_size):
for second_index in range(collection_size):
first_number = numbers[first_index]
second_number = numbers[second_index]
# The strong pair condition requires the absolute difference to be no more than the minimum value.
if abs(first_number - second_number) <= min(first_number, second_number):
# For any valid strong pair, we calculate its XOR to see if it's a new maximum.
current_pair_xor = first_number ^ second_number
# We update our record if the current pair's XOR is the largest we've encountered.
if current_pair_xor > maximum_xor_so_far:
maximum_xor_so_far = current_pair_xor
return maximum_xor_so_farThe values are sorted, and the answer is assembled from the high bit downward. For each bit, a trie is rebuilt by inserting the sorted values one at a time, while each node remembers the smallest and largest value in its subtree. A query walks the trie for the exclusive-or prefix under test and returns success as soon as the opposite branch contains a value no larger than the current number.
Here's how the algorithm would work step-by-step:
class TrieNode:
def __init__(self):
self.children = {}
self.min_value_in_subtree = float('inf')
self.max_value_in_subtree = float('-inf')
class Trie:
def __init__(self, bit_length):
self.root = TrieNode()
self.bit_length = bit_length
def insert(self, number):
current_node = self.root
for bit_position in range(self.bit_length - 1, -1, -1):
current_bit = (number >> bit_position) & 1
if current_bit not in current_node.children:
current_node.children[current_bit] = TrieNode()
current_node = current_node.children[current_bit]
current_node.min_value_in_subtree = min(current_node.min_value_in_subtree, number)
current_node.max_value_in_subtree = max(current_node.max_value_in_subtree, number)
def query(self, number_x, target_xor_prefix):
current_node = self.root
for bit_position in range(self.bit_length - 1, -1, -1):
if not current_node:
return False
target_xor_bit = (target_xor_prefix >> bit_position) & 1
bit_of_x = (number_x >> bit_position) & 1
# We need a number 'y' such that (bit_of_x ^ bit_of_y) = target_xor_bit.
required_bit_of_y = bit_of_x ^ target_xor_bit
# Check if a valid pair exists in the other branch of the Trie.
other_branch_node = current_node.children.get(1 - required_bit_of_y)
if other_branch_node and other_branch_node.min_value_in_subtree <= number_x:
return True
current_node = current_node.children.get(required_bit_of_y)
return False
class Solution:
def maximumStrongPairXor(self, nums):
sorted_numbers = sorted(nums)
max_possible_value = 2 * sorted_numbers[-1]
if max_possible_value == 0:
return 0
bit_length = max_possible_value.bit_length()
max_xor_result = 0
# Build the answer bit by bit, from most significant to least significant.
for bit_position in range(bit_length - 1, -1, -1):
potential_max_xor = max_xor_result | (1 << bit_position)
is_possible = False
# This structure will let us efficiently query for partners that satisfy the XOR prefix.
trie_for_prefixes = Trie(bit_length)
for number in sorted_numbers:
trie_for_prefixes.insert(number)
# For each number, we check if there's a previously inserted number that's a strong pair
# and also satisfies the potential maximum XOR we're currently testing.
if trie_for_prefixes.query(number, potential_max_xor):
is_possible = True
break
if is_possible:
max_xor_result = potential_max_xor
return max_xor_result| Case | How to Handle |
|---|---|
| The list contains one value | The direct search pairs that value with itself and records an exclusive-or of zero. |
| Two values are equal | Their exclusive-or is zero, so the direct search does not raise its maximum unless another strong pair is larger. |
| The values are too far apart for any mixed pair to be strong | The direct search returns zero, because only a value paired with itself qualifies. |
| A later strong pair has a larger exclusive-or than the pairs seen so far | Replace the recorded maximum with that pair's exclusive-or. |
| Twice the largest value is zero | Return zero from the bit search before any trie is built. |
| The trie query reports that the candidate prefix is possible | Keep that bit in the running answer and continue with the lower bits. |