Maximum Strong Pair XOR I - Practice Coding Problems

Maximum Strong Pair XOR I - Problem

Array Hash Table Bit Manipulation Trie Sliding Window Easy

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 Case

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

› Output: 1

💡 Note: Check all pairs: (1,1), (1,2), (2,2), (2,3), (3,3) are strong pairs. Among these, (2,3) gives maximum XOR: 2^3 = 1

Example 2 — Same Elements

$ Input: nums = [5,6,25,30]

› Output: 7

💡 Note: Strong pairs: (5,5), (6,6), (5,6), (25,25), (30,30). Maximum XOR is from (5,6): 5^6 = 3. Wait, let me recalculate: (5,6) gives 5^6=3, but we also need to check other combinations

Example 3 — Single Element

$ Input: nums = [10]

› Output: 0

💡 Note: Only one element, so only pair is (10,10). XOR of same numbers is 0: 10^10 = 0

Constraints

1 ≤ nums.length ≤ 50
1 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with integers

Find Strong Pairs

Identify pairs where |x-y| ≤ min(x,y)

Calculate XOR

Find maximum XOR among valid pairs

Key Takeaway

🎯 Key Insight: Strong pairs have the constraint |x - y| ≤ min(x, y), which significantly limits the search space

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that strong pairs satisfy |x - y| ≤ min(x, y), which limits valid pairs significantly. The brute force approach checks all pairs in O(n²) time. The sorted approach uses the property that for sorted elements x ≤ y, the condition becomes y ≤ 2x, allowing early termination. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sorted Approach	O(n²)	O(1)	Sort array first, then use the strong pair property to limit search
Brute Force	O(n²)	O(1)	Check all possible pairs and find maximum XOR among strong pairs

Sorted Approach — Algorithm Steps

Sort the array
For each element x, only check elements y where y <= 2x
Calculate XOR for valid pairs and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort elements in ascending order

Check Pairs

For each x, check y only while y ≤ 2x

Early Break

Break when y > 2x (no more strong pairs)

Code -

solution.c — C

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

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 n) {
    qsort(nums, n, sizeof(int), compare);
    int maxXor = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int x = nums[i], y = nums[j];
            // For sorted array: if y > 2*x, break
            if (y > 2 * x) {
                break;
            }
            maxXor = max_val(maxXor, x ^ y);
        }
    }
    
    return maxXor;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[count++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Sorting takes O(n log n), but nested loops still dominate with O(n²)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables, sorting can be done in-place

✓ Linear Space

26.3K Views

Medium Frequency

~15 min Avg. Time

847 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

Sorted Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler