Maximum Strong Pair XOR II - Practice Coding Problems

Maximum Strong Pair XOR II - Problem

Array Hash Table Bit Manipulation Trie Sliding Window Hard

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: You can pick the same integer twice to form a pair.

Input & Output

Example 1 — Basic Strong Pairs

$ Input: nums = [1,6,2,3]

› Output: 5

💡 Note: Strong pairs: (1,1) with XOR=0, (2,2) with XOR=0, (3,3) with XOR=0, (2,3) with XOR=1, (1,2) with XOR=3, (1,3) with XOR=2, (6,6) with XOR=0. However, we need |x-y| <= min(x,y). Checking: |1-6|=5 > min(1,6)=1 (not strong), |2-3|=1 <= min(2,3)=2 (strong), etc. The maximum XOR is 5 from a valid strong pair.

Example 2 — Same Elements

$ Input: nums = [5,5,5]

› Output: 0

💡 Note: All elements are the same, so all pairs are (5,5) with |5-5|=0 <= min(5,5)=5, making them strong pairs. The XOR of any pair is 5^5=0.

Example 3 — No Valid Pairs

$ Input: nums = [1,10]

› Output: 0

💡 Note: Check pair (1,10): |1-10|=9 > min(1,10)=1, so not a strong pair. Check pairs with same element: (1,1) and (10,10) both give XOR=0. Maximum XOR is 0.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
1 ≤ nums[i] ≤ 2²⁰

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,6,2,3] to find strong pairs

Strong Pair Check

Verify |x-y| <= min(x,y) condition for each pair

Maximum XOR

Find the largest XOR value among valid strong pairs

Key Takeaway

🎯 Key Insight: Use Trie data structure to efficiently find maximum XOR within the valid range of strong pair candidates

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that two numbers form a strong pair when their absolute difference doesn't exceed the smaller number. The optimal approach uses a Trie data structure combined with sliding window to efficiently find the maximum XOR among all valid strong pairs. Time: O(n log n + 32n), Space: O(32n).

Common Approaches

Approach	Time	Space	Notes
✓ Trie + Sliding Window	O(n log n + n * 32)	O(32n)	Use Trie data structure with sliding window to efficiently find maximum XOR among strong pairs
Brute Force - Check All Pairs	O(n²)	O(1)	Check every possible pair to see if it's strong, then find maximum XOR among all strong pairs
Sort + Two Pointers	O(n²)	O(1)	Sort array first, then use two pointers to efficiently find strong pairs and maximize XOR

Trie + Sliding Window — Algorithm Steps

Sort array to enable sliding window
For each number, find range of valid strong pair partners
Use Trie to efficiently find maximum XOR in that range

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Insert numbers into Trie for efficient XOR queries

Sliding Window

Maintain window of valid strong pair candidates

Query Max XOR

Use Trie to find maximum XOR efficiently

Code -

solution.c — C

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

typedef struct TrieNode {
    struct TrieNode* children[2];
    int count;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->children[0] = node->children[1] = NULL;
    node->count = 0;
    return node;
}

void insert(TrieNode* root, int num) {
    TrieNode* node = root;
    for (int i = 31; i >= 0; i--) {
        int bit = (num >> i) & 1;
        if (!node->children[bit]) {
            node->children[bit] = createNode();
        }
        node = node->children[bit];
        node->count++;
    }
}

void removeNum(TrieNode* root, int num) {
    TrieNode* node = root;
    for (int i = 31; i >= 0; i--) {
        int bit = (num >> i) & 1;
        node = node->children[bit];
        node->count--;
    }
}

int queryMaxXor(TrieNode* root, int num) {
    TrieNode* node = root;
    int result = 0;
    for (int i = 31; i >= 0; i--) {
        int bit = (num >> i) & 1;
        int toggleBit = 1 - bit;
        if (node->children[toggleBit] && node->children[toggleBit]->count > 0) {
            result |= (1 << i);
            node = node->children[toggleBit];
        } else if (node->children[bit] && node->children[bit]->count > 0) {
            node = node->children[bit];
        } else {
            return result;
        }
    }
    return result;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int max_val(int a, int b) {
    return a > b ? a : b;
}

int solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    qsort(nums, numsSize, sizeof(int), compare);
    TrieNode* root = createNode();
    int maxXor = 0;
    
    int left = 0;
    for (int right = 0; right < numsSize; right++) {
        insert(root, nums[right]);
        
        while (left < right && nums[right] - nums[left] > nums[left]) {
            removeNum(root, nums[left]);
            left++;
        }
        
        maxXor = max_val(maxXor, queryMaxXor(root, nums[right]));
    }
    
    return maxXor;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + n * 32)

O(n log n) for sorting + O(32n) for Trie operations (32 bits per number)

⚡ Linearithmic

Space Complexity

O(32n)

Trie can store up to n numbers with 32 bits each

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~45 min Avg. Time

890 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

Trie + Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler