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] <= 108In #2317 Maximum XOR After Operations, the key observation comes from understanding how bitwise operations affect the final XOR. Instead of simulating every possible operation, analyze how individual bits behave across the array.
Each operation allows you to redistribute existing bits between numbers without introducing new ones. Therefore, if a particular bit appears in any number in the array, it can potentially contribute to the final XOR result. The optimal strategy is to determine which bits can survive and appear in the final configuration.
The core insight is that the maximum achievable XOR equals the bitwise OR of all elements in the array. By aggregating bits from all numbers, we capture every bit that can possibly remain set after optimal operations.
This leads to a very efficient solution: iterate through the array and compute the cumulative OR. The approach runs in O(n) time with O(1) extra space, making it ideal even for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bitwise OR aggregation of all elements | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Consider what it means to be able to choose any x for the operation and which integers could be obtained from a given nums[i].
The given operation can unset any bit in nums[i].
The nth bit of the XOR of all the elements is 1 if the nth bit is 1 for an odd number of elements. When can we ensure it is odd?
Try to set every bit of the result to 1 if possible.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems involving bit manipulation and XOR logic are common in FAANG-style interviews. While this exact question may not always appear, the underlying concepts of bitwise reasoning and optimization are frequently tested.
The optimal approach relies on a bit manipulation insight. The maximum possible XOR after allowed operations equals the bitwise OR of all elements in the array. By iterating through the array and accumulating the OR value, you obtain the answer in linear time.
Any bit that appears in at least one number can potentially remain set in the final configuration after operations. Since operations only redistribute or remove bits but never introduce new ones, the OR of all elements represents the maximum set of bits achievable.
No special data structure is required for this problem. A simple integer variable to store the cumulative bitwise OR while iterating through the array is sufficient, making the solution both space-efficient and straightforward.