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 II

Number: 3197

Difficulty: Hard

Paid? No

Companies: ZScaler

Problem Description

Given a 0-indexed integer array nums, a pair (x, y) is called a strong pair if when letting a = min(x, y) and b = max(x, y) the condition b – a <= a holds. In other words, for any pair chosen from nums, once sorted (x <= y), it must satisfy y <= 2 * x. Note that you can pick the same integer twice. The task is to select two integers from nums such that they form a strong pair and their bitwise XOR is maximum of all strong pairs present, and return that maximum XOR value.

Key Insights

  • When x <= y, the condition |x – y| <= min(x, y) can be rewritten as y – x <= x, which simplifies to y <= 2 * x.
  • Sorting the array lets us quickly understand the relationship between the smallest and largest in a candidate set.
  • If a contiguous subarray (window) in the sorted array satisfies nums[right] <= 2 * nums[left], then every pair in that window satisfies the strong pair condition.
  • Using a sliding window along with a bitwise trie (prefix tree) allows us to maintain a dynamic set of candidates and efficiently query for the best XOR partner.
  • The trie supports insertion and deletion (by maintaining counts) so that we can “slide” the window while preserving only those numbers that form valid pairs with the current candidate.
  • For each new number added, we query the trie to find the number already in the window that produces the highest XOR value with it. Since a valid pair may be formed by a number with itself (yielding 0), we always have a fallback.

Space and Time Complexity

Time Complexity: O(n · B), where n is the length of nums and B is the number of bits (up to 20) since each insert, remove, and query in the trie costs O(B)
Space Complexity: O(n · B) in the worst case for storing numbers in the trie, though typically limited by the range of bits

Solution

  1. First, sort the array nums.
  2. Use two pointers (L and R) to maintain a sliding window. The window [L,R] is valid when nums[R] <= 2 * nums[L]; this guarantees that every pair (a, b) within the window is strong.
  3. Use a trie (bitwise prefix tree) that supports insertion and removal to maintain the numbers in the current window. Each trie node will store a count of how many numbers go through that node so that deletions are possible.
  4. For each new number at index R:
    • Insert nums[R] into the trie.
    • While the current window is not valid (i.e. nums[R] > 2 * nums[L]), remove nums[L] from the trie and increment L.
    • Query the trie for the best XOR partner of nums[R] (this finds a number in the current window that maximizes nums[R] XOR candidate).
    • Update the global maximum XOR value accordingly.
  5. Finally, return the global maximum XOR value.

This solution leverages both the sliding window technique (to guarantee the strong pair condition across all pairs in the window) and the trie (to efficiently compute the maximum XOR pair in the current valid window).

Code Solutions

# Python solution with detailed comments

class TrieNode:
    def __init__(self):
        # Dictionary children: keys '0' and '1'
        self.children = {}
        # Count of numbers passing through this node
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()
        # Considering numbers are up to 20 bits (2^20 - 1)
        self.B = 20

    def insert(self, num):
        node = self.root
        for i in range(self.B - 1, -1, -1):
            # Get the i-th bit (0 or 1)
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]
            node.count += 1

    def remove(self, num):
        node = self.root
        for i in range(self.B - 1, -1, -1):
            bit = (num >> i) & 1
            next_node = node.children[bit]
            next_node.count -= 1
            # Optionally prune the node if count becomes 0.
            if next_node.count == 0:
                del node.children[bit]
                return
            node = next_node

    def query(self, num):
        # Query maximum XOR for num from numbers in the trie.
        node = self.root
        xor_val = 0
        for i in range(self.B - 1, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            # Prefer the branch that gives a 1 in the XOR result
            if toggled_bit in node.children:
                xor_val |= (1 << i)
                node = node.children[toggled_bit]
            elif bit in node.children:
                node = node.children[bit]
            else:
                break
        return xor_val

def maximumStrongPairXor(nums):
    # Sort the array to use sliding window based on the valid condition.
    nums.sort()
    trie = Trie()
    L = 0
    max_xor = 0

    for R in range(len(nums)):
        # Insert the new number into the trie.
        trie.insert(nums[R])
        # Ensure that our current window [L, R] is valid:
        # For the smallest number in the window (nums[L]), 
        # it must hold that nums[R] <= 2 * nums[L]
        while nums[R] > 2 * nums[L]:
            trie.remove(nums[L])
            L += 1
        # Query the trie for best XOR with current number.
        current_xor = trie.query(nums[R])
        max_xor = max(max_xor, current_xor)
    return max_xor

# Example usage:
if __name__ == "__main__":
    print(maximumStrongPairXor([1,2,3,4,5]))   # Expected output: 7
    print(maximumStrongPairXor([10,100]))        # Expected output: 0
    print(maximumStrongPairXor([500,520,2500,3000]))  # Expected output: 1020
← Back to All Questions