2935. Maximum Strong Pair XOR II LeetCode Solution
In this guide, you will get 2935. Maximum Strong Pair XOR II LeetCode Solution with the best time and space complexity. The solution to Maximum Strong Pair XOR II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 that you can pick the same integer twice to form a pair.
Example 1:
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:
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:
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.
2935. Maximum Strong Pair XOR II LeetCode Solution in C++
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
TrieNode() : children(2) {}
int mn = INT_MAX;
int mx = INT_MIN;
};
class BitTrie {
public:
BitTrie(int maxBit) : maxBit(maxBit) {}
void insert(int num) {
shared_ptr<TrieNode> node = root;
for (int i = maxBit; i >= 0; --i) {
const int bit = num >> i & 1;
if (node->children[bit] == nullptr)
node->children[bit] = make_shared<TrieNode>();
node = node->children[bit];
node->mn = min(node->mn, num);
node->mx = max(node->mx, num);
}
}
// Returns max(x ^ y), where |x - y| <= min(x, y).
//
// If x <= y, |x - y| <= min(x, y) can be written as y - x <= x.
// So, y <= 2 * x.
int getMaxXor(int x) {
int maxXor = 0;
shared_ptr<TrieNode> node = root;
for (int i = maxBit; i >= 0; --i) {
const int bit = x >> i & 1;
const int toggleBit = bit ^ 1;
// If `node.children[toggleBit].max > x`, it means there's a number in the
// node that satisfies the condition to ensure that x <= y among x and y.
// If `node.children[toggleBit].min <= 2 * x`, it means there's a number
// in the node that satisfies the condition for a valid y.
if (node->children[toggleBit] != nullptr &&
node->children[toggleBit]->mx > x &&
node->children[toggleBit]->mn <= 2 * x) {
maxXor = maxXor | 1 << i;
node = node->children[toggleBit];
} else if (node->children[bit] != nullptr) {
node = node->children[bit];
} else { // There's nothing in the Bit Trie.
return 0;
}
}
return maxXor;
}
private:
const int maxBit;
shared_ptr<TrieNode> root = make_shared<TrieNode>();
};
class Solution {
public:
// Same as 2932. Maximum Strong Pair XOR I
int maximumStrongPairXor(vector<int>& nums) {
const int maxNum = ranges::max(nums);
const int maxBit = static_cast<int>(log2(maxNum));
int ans = 0;
BitTrie bitTrie(maxBit);
for (const int num : nums)
bitTrie.insert(num);
for (const int num : nums)
ans = max(ans, bitTrie.getMaxXor(num));
return ans;
}
}; /* code provided by PROGIEZ */
2935. Maximum Strong Pair XOR II LeetCode Solution in Java
class TrieNode {
public TrieNode[] children = new TrieNode[2];
public int mn = Integer.MAX_VALUE;
public int mx = Integer.MIN_VALUE;
}
class BitTrie {
public BitTrie(int maxBit) {
this.maxBit = maxBit;
}
public void insert(int num) {
TrieNode node = root;
for (int i = maxBit; i >= 0; --i) {
final int bit = (int) (num >> i & 1);
if (node.children[bit] == null)
node.children[bit] = new TrieNode();
node = node.children[bit];
node.mn = Math.min(node.mn, num);
node.mx = Math.max(node.mx, num);
}
}
// Returns max(x ^ y), where |x - y| <= min(x, y).
//
// If x <= y, |x - y| <= min(x, y) can be written as y - x <= x.
// So, y <= 2 * x.
public int getMaxXor(int x) {
int maxXor = 0;
TrieNode node = root;
for (int i = maxBit; i >= 0; --i) {
final int bit = (int) (x >> i & 1);
final int toggleBit = bit ^ 1;
// If `node.children[toggleBit].mx > x`, it means there's a number in the
// node that satisfies the condition to ensure that x <= y among x and y.
// If `node.children[toggleBit].mn <= 2 * x`, it means there's a number
// in the node that satisfies the condition for a valid y.
if (node.children[toggleBit] != null && node.children[toggleBit].mx > x &&
node.children[toggleBit].mn <= 2 * x) {
maxXor = maxXor | 1 << i;
node = node.children[toggleBit];
} else if (node.children[bit] != null) {
node = node.children[bit];
} else { // There's nothing in the Bit Trie.
return 0;
}
}
return maxXor;
}
private int maxBit;
private TrieNode root = new TrieNode();
}
class Solution {
// Same as 2932. Maximum Strong Pair XOR I
public int maximumStrongPairXor(int[] nums) {
final int maxNum = Arrays.stream(nums).max().getAsInt();
final int maxBit = (int) (Math.log(maxNum) / Math.log(2));
int ans = 0;
BitTrie bitTrie = new BitTrie(maxBit);
for (final int num : nums)
bitTrie.insert(num);
for (final int num : nums)
ans = Math.max(ans, bitTrie.getMaxXor(num));
return ans;
}
} // code provided by PROGIEZ
2935. Maximum Strong Pair XOR II LeetCode Solution in Python
class TrieNode:
def __init__(self):
self.children: list[TrieNode | None] = [None] * 2
self.mn = math.inf
self.mx = -math.inf
class BitTrie:
def __init__(self, maxBit: int):
self.maxBit = maxBit
self.root = TrieNode()
def insert(self, num: int) -> None:
node = self.root
for i in range(self.maxBit, -1, -1):
bit = num >> i & 1
if not node.children[bit]:
node.children[bit] = TrieNode()
node = node.children[bit]
node.mn = min(node.mn, num)
node.mx = max(node.mx, num)
def getMaxXor(self, x: int) -> int:
"""Returns max(x ^ y) where |x - y| <= min(x, y).
If x <= y, |x - y| <= min(x, y) can be written as y - x <= x.
So, y <= 2 * x.
"""
maxXor = 0
node = self.root
for i in range(self.maxBit, -1, -1):
bit = x >> i & 1
toggleBit = bit ^ 1
# If `node.children[toggleBit].mx > x`, it means there's a number in the
# node that satisfies the condition to ensure that x <= y among x and y.
# If `node.children[toggleBit].mn <= 2 * x`, it means there's a number in
# the node that satisfies the condition for a valid y.
if (node.children[toggleBit] and
node.children[toggleBit].mx > x and
node.children[toggleBit].mn <= 2 * x):
maxXor = maxXor | 1 << i
node = node.children[toggleBit]
elif node.children[bit]:
node = node.children[bit]
else: # There's nothing in the Bit Trie.
return 0
return maxXor
class Solution:
# Same as 2932. Maximum Strong Pair XOR I
def maximumStrongPairXor(self, nums: list[int]) -> int:
maxNum = max(nums)
maxBit = int(math.log2(maxNum))
bitTrie = BitTrie(maxBit)
for num in nums:
bitTrie.insert(num)
return max(bitTrie.getMaxXor(num) for num in nums) # code by PROGIEZ
