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.
Solutions
Solution
class Solution {public int maximumXOR(int[] nums) { int ans = 0; for (int x : nums) { ans |= x; } return ans; }}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.