Maximum XOR With an Element From Array - Practice Coding Problems

Maximum XOR With an Element From Array - Problem

You are given an array nums consisting of non-negative integers. You are also given a queries array, where queries[i] = [xi, mi].

The answer to the ith query is the maximum bitwise XOR value of xi and any element of nums that does not exceed mi. In other words, the answer is max(nums[j] XOR xi) for all j such that nums[j] <= mi. If all elements in nums are larger than mi, then the answer is -1.

Return an integer array answer where answer.length == queries.length and answer[i] is the answer to the ith query.

Input & Output

Example 1 — Basic Queries

$ Input: nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]

› Output: [3,3,7]

💡 Note: Query [3,1]: Valid elements ≤1 are {0,1}. Max XOR: max(0⊕3, 1⊕3) = max(3,2) = 3. Query [1,3]: Valid elements ≤3 are {0,1,2,3}. Max XOR: max(0⊕1, 1⊕1, 2⊕1, 3⊕1) = max(1,0,3,2) = 3. Query [5,6]: All elements ≤6, Max XOR: max(0⊕5, 1⊕5, 2⊕5, 3⊕5, 4⊕5) = max(5,4,7,6,1) = 7.

Example 2 — No Valid Elements

$ Input: nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]

› Output: [15,-1,4]

💡 Note: Query [12,4]: Valid elements ≤4 are {2,4,3}. Max XOR: max(2⊕12, 4⊕12, 3⊕12) = max(14,8,15) = 15. Query [8,1]: No elements ≤1, return -1. Query [6,3]: Valid elements ≤3 are {2,3}. Max XOR: max(2⊕6, 3⊕6) = max(4,5) = 5.

Example 3 — Edge Case

$ Input: nums = [0], queries = [[0,0]]

› Output: [0]

💡 Note: Single element case: 0 ≤ 0, so 0 XOR 0 = 0.

Constraints

1 ≤ nums.length, queries.length ≤ 10⁵
queries[i].length == 2
0 ≤ nums[j], xi, mi ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and queries with [xi, mi] pairs

Filter

For each query, find elements ≤ mi

Maximize XOR

Compute maximum XOR of xi with valid elements

Key Takeaway

🎯 Key Insight: Use trie structure to efficiently maximize XOR while respecting value constraints

Asked in

G Google 15 M Microsoft 12 a Amazon 8 f Facebook 6

The key insight is to use a trie (prefix tree) data structure to efficiently find maximum XOR values while respecting the constraint that elements must not exceed the given limit. The optimal approach builds a trie with constraint tracking, enabling O(30) per query complexity. Time: O((n+m)×30), Space: O(n×30).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × m)	O(1)	For each query, check all valid elements and find maximum XOR
Trie with Offline Processing	O((n + m) × 30)	O(n × 30)	Build trie with sorted elements, process queries offline for optimal XOR search
Sort with Binary Search	O(n log n + m × n)	O(1)	Sort nums, then use binary search to find valid elements for each query

Brute Force — Algorithm Steps

For each query [xi, mi]
Check all nums[j] where nums[j] <= mi
Compute nums[j] XOR xi for each valid j
Return maximum XOR found, or -1 if none

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Processing

For each query [xi, mi], filter valid elements

XOR Calculation

Compute XOR with xi for each valid element

Maximum Selection

Return the maximum XOR value found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int** queries, int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    int* result = (int*)malloc(queriesSize * sizeof(int));
    
    for (int i = 0; i < queriesSize; i++) {
        int xi = queries[i][0];
        int mi = queries[i][1];
        int maxXor = -1;
        
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] <= mi) {
                int xor = nums[j] ^ xi;
                if (xor > maxXor) {
                    maxXor = xor;
                }
            }
        }
        result[i] = maxXor;
    }
    return result;
}

int main() {
    // Simple parsing for demonstration
    int nums[] = {0, 1, 2, 3, 4};
    int* queries[2];
    queries[0] = (int[]){3, 1};
    queries[1] = (int[]){1, 3};
    
    int returnSize;
    int* result = solution(nums, 5, queries, 2, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each of m queries, we check all n elements

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track maximum

✓ Linear Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler