22 Mar 2025•Python•Unknown

Maximum Xor With An Element From Array

notes and solution files for maximum xor with an element from array.

this entry collects the solution files i have for maximum xor with an element from array. i may expand it with a fuller write-up later, but the implementation files are already here.

available solution files

Python maximum-xor-with-an-element-from-array/solution.py

Solution files

Python•maximum-xor-with-an-element-from-array/solution.py

from typing import List, Tuple


class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        nums.sort()
        paired: List[Tuple[int, int, int]] = [
            (limit, value, idx) for idx, (value, limit) in enumerate(queries)
        ]
        paired.sort()

        trie = _BitTrie()
        answers = [-class="syntax-number">1] * len(queries)
        i = class="syntax-number">0

        for limit, value, idx in paired:
            while i < len(nums) and nums[i] <= limit:
                trie.add(nums[i])
                i += class="syntax-number">1

            answers[idx] = trie.max_xor(value)

        return answers


class _BitTrie:
    def __init__(self) -> None:
        self.root: dict[int, dict] = {}
        self.has_values = False

    def add(self, number: int) -> None:
        node = self.root
        for bit in range(class="syntax-number">31, -class="syntax-number">1, -class="syntax-number">1):
            branch = (number >> bit) & class="syntax-number">1
            if branch not in node:
                node[branch] = {}
            node = node[branch]
        self.has_values = True

    def max_xor(self, number: int) -> int:
        if not self.has_values:
            return -class="syntax-number">1

        node = self.root
        answer = class="syntax-number">0
        for bit in range(class="syntax-number">31, -class="syntax-number">1, -class="syntax-number">1):
            want = class="syntax-number">1 - ((number >> bit) & class="syntax-number">1)
            if want in node:
                answer |= class="syntax-number">1 << bit
                node = node[want]
            else:
                node = node.get(class="syntax-number">1 - want, node)
        return answer