Problem

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 _themaximum _XOR value out of all possible strong pairs in the array nums.

Note that you can pick the same integer twice to form a pair.

Examples

Example 1

1
2
3
4

Input: nums = [1,2,3,4,5]
Output: 7
Explanation: There are 11 strong pairs in the array nums: (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) and (5, 5).
The maximum XOR possible from these pairs is 3 XOR 4 = 7.

Example 2

1
2
3
4

Input: nums = [10,100]
Output: 0
Explanation: There are 2 strong pairs in the array nums: (10, 10) and (100, 100).
The maximum XOR possible from these pairs is 10 XOR 10 = 0 since the pair (100, 100) also gives 100 XOR 100 = 0.

Example 3

1
2
3
4

Input: nums = [500,520,2500,3000]
Output: 1020
Explanation: There are 6 strong pairs in the array nums: (500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) and (3000, 3000).
The maximum XOR possible from these pairs is 500 XOR 520 = 1020 since the only other non-zero XOR value is 2500 XOR 3000 = 636.

Constraints

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 220 - 1

Solution

Method 1 – Trie with Sliding Window

Intuition

To maximize the XOR for strong pairs efficiently, sort the array and use a sliding window to maintain the valid range for each number. For each number, use a trie to quickly find the number in the window that gives the maximum XOR.

Approach

  1. Sort nums.
  2. For each x in nums, maintain a window of numbers y such that |x - y| <= min(x, y) (which, after sorting, is y >= x - y and y <= x + y).
  3. Use a trie to insert numbers in the window and query for the maximum XOR with x.
  4. Slide the window as you iterate, removing numbers that are no longer valid.
  5. Return the maximum XOR found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

struct TrieNode {
    TrieNode* child[2] = {};
};
class Solution {
public:
    int maximumStrongPairXor(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0, l = 0;
        TrieNode* root = new TrieNode();
        auto insert = [&](int x) {
            TrieNode* node = root;
            for (int i = 16; i >= 0; --i) {
                int b = (x >> i) & 1;
                if (!node->child[b]) node->child[b] = new TrieNode();
                node = node->child[b];
            }
        };
        auto query = [&](int x) {
            TrieNode* node = root;
            int res = 0;
            for (int i = 16; i >= 0; --i) {
                int b = (x >> i) & 1;
                if (node->child[!b]) {
                    res |= (1 << i);
                    node = node->child[!b];
                } else node = node->child[b];
            }
            return res;
        };
        for (int r = 0; r < n; ++r) {
            while (l < r && nums[r] - nums[l] > nums[l]) ++l;
            TrieNode* tmp = new TrieNode();
            for (int i = l; i < r; ++i) insert(nums[i]);
            if (r > l) ans = max(ans, query(nums[r]));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import "sort"
type Trie struct{child [2]*Trie}
func (t *Trie) Insert(x int) {
    node := t
    for i := 16; i >= 0; i-- {
        b := (x >> i) & 1
        if node.child[b] == nil {
            node.child[b] = &Trie{}
        }
        node = node.child[b]
    }
}
func (t *Trie) Query(x int) int {
    node := t; res := 0
    for i := 16; i >= 0; i-- {
        b := (x >> i) & 1
        if node.child[1-b] != nil {
            res |= 1 << i
            node = node.child[1-b]
        } else {
            node = node.child[b]
        }
    }
    return res
}
func maximumStrongPairXor(nums []int) int {
    sort.Ints(nums)
    n, ans, l := len(nums), 0, 0
    for r := 0; r < n; r++ {
        for l < r && nums[r]-nums[l] > nums[l] { l++ }
        trie := &Trie{}
        for i := l; i < r; i++ { trie.Insert(nums[i]) }
        if r > l { ans = max(ans, trie.Query(nums[r])) }
    }
    return ans
}
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import java.util.*;
class Trie {
    Trie[] child = new Trie[2];
}
class Solution {
    public int maximumStrongPairXor(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0, l = 0;
        for (int r = 0; r < n; ++r) {
            while (l < r && nums[r] - nums[l] > nums[l]) ++l;
            Trie root = new Trie();
            for (int i = l; i < r; ++i) insert(root, nums[i]);
            if (r > l) ans = Math.max(ans, query(root, nums[r]));
        }
        return ans;
    }
    void insert(Trie root, int x) {
        Trie node = root;
        for (int i = 16; i >= 0; --i) {
            int b = (x >> i) & 1;
            if (node.child[b] == null) node.child[b] = new Trie();
            node = node.child[b];
        }
    }
    int query(Trie root, int x) {
        Trie node = root; int res = 0;
        for (int i = 16; i >= 0; --i) {
            int b = (x >> i) & 1;
            if (node.child[1-b] != null) {
                res |= 1 << i;
                node = node.child[1-b];
            } else node = node.child[b];
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Trie { val child = arrayOfNulls<Trie>(2) }
class Solution {
    fun maximumStrongPairXor(nums: IntArray): Int {
        nums.sort()
        var ans = 0; var l = 0
        for (r in nums.indices) {
            while (l < r && nums[r] - nums[l] > nums[l]) l++
            val root = Trie()
            for (i in l until r) insert(root, nums[i])
            if (r > l) ans = maxOf(ans, query(root, nums[r]))
        }
        return ans
    }
    fun insert(root: Trie, x: Int) {
        var node = root
        for (i in 16 downTo 0) {
            val b = (x shr i) and 1
            if (node.child[b] == null) node.child[b] = Trie()
            node = node.child[b]!!
        }
    }
    fun query(root: Trie, x: Int): Int {
        var node = root; var res = 0
        for (i in 16 downTo 0) {
            val b = (x shr i) and 1
            if (node.child[1-b] != null) {
                res = res or (1 shl i)
                node = node.child[1-b]!!
            } else node = node.child[b]!!
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Trie:
    def __init__(self):
        self.child = [None, None]
class Solution:
    def maximumStrongPairXor(self, nums: list[int]) -> int:
        nums.sort()
        ans, l = 0, 0
        for r, x in enumerate(nums):
            while l < r and x - nums[l] > nums[l]:
                l += 1
            root = Trie()
            for i in range(l, r):
                node = root
                for b in range(16, -1, -1):
                    bit = (nums[i] >> b) & 1
                    if not node.child[bit]:
                        node.child[bit] = Trie()
                    node = node.child[bit]
            if r > l:
                node = root
                res = 0
                for b in range(16, -1, -1):
                    bit = (x >> b) & 1
                    if node.child[1-bit]:
                        res |= 1 << b
                        node = node.child[1-bit]
                    else:
                        node = node.child[bit]
                ans = max(ans, res)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

struct Trie { child: [Option<Box<Trie>>; 2] }
impl Trie { fn new() -> Self { Trie { child: [None, None] } } }
impl Solution {
    pub fn maximum_strong_pair_xor(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        nums.sort();
        let mut ans = 0;
        let mut l = 0;
        for r in 0..nums.len() {
            while l < r && nums[r] - nums[l] > nums[l] { l += 1; }
            let mut root = Trie::new();
            for i in l..r {
                let mut node = &mut root;
                for b in (0..=16).rev() {
                    let bit = (nums[i] >> b) & 1;
                    node = node.child[bit as usize].get_or_insert_with(|| Box::new(Trie::new()));
                }
            }
            if r > l {
                let mut node = &root;
                let mut res = 0;
                for b in (0..=16).rev() {
                    let bit = (nums[r] >> b) & 1;
                    if let Some(ref next) = node.child[1-bit as usize] {
                        res |= 1 << b;
                        node = next;
                    } else if let Some(ref next) = node.child[bit as usize] {
                        node = next;
                    }
                }
                ans = ans.max(res);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Trie { child: [Trie?, Trie?] = [undefined, undefined]; }
class Solution {
    maximumStrongPairXor(nums: number[]): number {
        nums.sort((a, b) => a - b);
        let ans = 0, l = 0;
        for (let r = 0; r < nums.length; ++r) {
            while (l < r && nums[r] - nums[l] > nums[l]) ++l;
            const root = new Trie();
            for (let i = l; i < r; ++i) {
                let node = root;
                for (let b = 16; b >= 0; --b) {
                    const bit = (nums[i] >> b) & 1;
                    if (!node.child[bit]) node.child[bit] = new Trie();
                    node = node.child[bit]!;
                }
            }
            if (r > l) {
                let node = root, res = 0;
                for (let b = 16; b >= 0; --b) {
                    const bit = (nums[r] >> b) & 1;
                    if (node.child[1-bit]) {
                        res |= 1 << b;
                        node = node.child[1-bit]!;
                    } else {
                        node = node.child[bit]!;
                    }
                }
                ans = Math.max(ans, res);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 log M), where n is the length of nums and M is the max value in nums. For each number, we may build a trie of up to n numbers, each with up to log M bits.
  • 🧺 Space complexity: O(n log M), for the trie at each step.