Maximum XOR After Operations
MedPrompt
You are given a 0-indexed integer array nums. In one operation, select any non-negative integer x and an index i, then update nums[i] to be equal to nums[i] AND (nums[i] XOR x).
Note that AND is the bitwise AND operation and XOR is the bitwise XOR operation.
Return the maximum possible bitwise XOR of all elements of nums after applying the operation any number of times.
Example 1:
Input: nums = [3,2,4,6]
Output: 7
Explanation: Apply the operation with x = 4 and i = 3, num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2.
Now, nums = [3, 2, 4, 2] and the bitwise XOR of all the elements = 3 XOR 2 XOR 4 XOR 2 = 7.
It can be shown that 7 is the maximum possible bitwise XOR.
Note that other operations may be used to achieve a bitwise XOR of 7.Example 2:
Input: nums = [1,2,3,9,2]
Output: 11
Explanation: Apply the operation zero times.
The bitwise XOR of all the elements = 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11.
It can be shown that 11 is the maximum possible bitwise XOR.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 108
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly models the problem after analyzing the core operation. The operation nums[i] = nums[i] AND (nums[i] XOR x) allows us to transform nums[i] into any of its "submasks". A number y is a submask of nums[i] if all set bits in y are also set in nums[i]. The problem then becomes: for each nums[i], choose one of its submasks nums[i]' such that the total XOR sum nums[0]' XOR nums[1]' XOR ... is maximized. The brute-force method explores every possible combination of submasks.
Algorithm
- Define a recursive function
solve(index, currentXOR). - Base Case: If
indexequals the length ofnums, update the global maximum XOR value withcurrentXORand return. - Recursive Step: For the number
nums[index], iterate through all its submaskss. For eachs, recursively callsolve(index + 1, currentXOR ^ s).
Walkthrough
We can define a recursive function, say findMaxXOR(index, currentXOR), to explore all possibilities.
The function takes the current index index in the nums array and the currentXOR sum of the submasks chosen for elements from 0 to index-1.
The base case for the recursion is when index reaches the end of the array. At this point, we compare currentXOR with a global maximum and update it if necessary.
In the recursive step, for the number nums[index], we first generate all of its possible submasks. Then, for each submask s, we make a recursive call findMaxXOR(index + 1, currentXOR ^ s).
Generating submasks for a number n can be done by iterating s from n down to 0 and taking only those s where (s & n) == s. A more efficient way is for (int s = n; s > 0; s = (s - 1) & n).
The initial call would be findMaxXOR(0, 0).
class Solution { int max_xor = 0; public int maximumXOR(int[] nums) { // This approach is too slow and will cause a Time Limit Exceeded error. // It is for demonstration purposes only. findMaxXOR(nums, 0, 0); return max_xor; } private void findMaxXOR(int[] nums, int index, int currentXOR) { if (index == nums.length) { if (currentXOR > max_xor) { max_xor = currentXOR; } return; } int n = nums[index]; // Iterate through all submasks of n, including 0 int s = n; while (s > 0) { findMaxXOR(nums, index + 1, currentXOR ^ s); s = (s - 1) & n; } // Case for submask 0 findMaxXOR(nums, index + 1, currentXOR ^ 0); }}Complexity
Time
O(product(2^popcount(nums[i]))). `popcount(n)` is the number of set bits in `n`. In the worst case, this is exponential in the sum of set bits of all numbers, which is far too slow for the given constraints.
Space
O(N) for the recursion stack depth, where N is the number of elements in `nums`.
Trade-offs
Pros
It's a conceptually straightforward approach that directly follows from the problem definition.
Cons
The time complexity is prohibitively high, making it infeasible for the given constraints.
It will result in a "Time Limit Exceeded" error on any reasonably sized input.
This highly efficient approach stems from a key insight into the properties of the given operation and the goal of maximizing a bitwise XOR sum. The core idea is to analyze the problem on a bit-by-bit basis.
Algorithm
- Initialize an integer variable
resto 0. - Iterate through each number
numin the input arraynums. - For each
num, updateresby performing a bitwise OR operation:res = res | num. - After the loop finishes,
reswill hold the bitwise OR of all elements. - Return
res.
Walkthrough
First, let's analyze the operation: new_val = val AND (val XOR x).
Let's consider the k-th bit. If the k-th bit of val is 0, the k-th bit of new_val will be 0 AND (0 XOR x_k) = 0. This means a 0-bit can never be turned into a 1-bit.
If the k-th bit of val is 1, the k-th bit of new_val will be 1 AND (1 XOR x_k). By choosing x_k=0, the result is 1 AND 1 = 1. By choosing x_k=1, the result is 1 AND 0 = 0. This means we can freely change any 1-bit to a 0-bit, or keep it as a 1.
In summary, for any number nums[i], we can change it to any of its submasks (i.e., turn any of its set bits off).
Our goal is to maximize the final XOR sum S = nums[0]' XOR ... XOR nums[n-1]'. To maximize S, we want to set as many of its most significant bits to 1 as possible.
Consider the k-th bit of the result, S_k. Can we make S_k = 1? This requires an odd number of nums[i]'_k to be 1. A bit nums[i]'_k can be 1 only if the original nums[i]_k was 1.
If for a given bit k, at least one number nums[j] has its k-th bit set (nums[j]_k = 1), we can achieve S_k = 1. We do this by choosing nums[j]' to have its k-th bit as 1, and for all other numbers nums[i]' (where i != j), we choose their k-th bit to be 0 (which is always possible). The XOR sum of these k-th bits will be 1.
If for a given bit k, no number nums[i] has its k-th bit set, then nums[i]_k is 0 for all i. Consequently, nums[i]'_k must also be 0 for all i, and S_k will be 0.
Therefore, the k-th bit of the maximum possible XOR sum is 1 if and only if the k-th bit is 1 in at least one of the original numbers. This is precisely the definition of the bitwise OR operation.
The maximum XOR sum is simply the bitwise OR of all elements in the nums array.
The algorithm is to iterate through the array and compute the cumulative bitwise OR.
class Solution { public int maximumXOR(int[] nums) { int result = 0; for (int num : nums) { result |= num; } return result; }}Complexity
Time
O(N), where N is the number of elements in `nums`. We perform a single pass through the array.
Space
O(1). We only use a single integer variable for storage, regardless of the input size.
Trade-offs
Pros
Optimal time and space complexity.
The solution is simple and elegant.
Cons
The solution relies on a non-obvious insight about the bitwise operations, which might not be easy to derive under pressure.
Solutions
Solution
class Solution {public int maximumXOR(int[] nums) { int ans = 0; for (int x : nums) { ans |= x; } return ans; }}class Solution { public: int maximumXOR ( vector < int >& nums ) { int ans = 0 ; for ( int & x : nums ) { ans |= x ; } return ans ; } };class Solution: def maximumXOR(self, nums: List[int]) -> int: return reduce(or_, nums)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.