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] <= 108Problem Overview: You can repeatedly choose two indices i and j and replace nums[i] with nums[i] & nums[j]. After any number of operations, compute the maximum possible XOR of all elements in the array. The challenge is understanding how the AND operation changes individual bits and how that affects the final XOR.
Approach 1: Optimize Using XOR Properties (O(n) time, O(1) space)
The key observation is that the operation a = a & b can only turn bits off, never on. However, you can strategically apply operations so that a chosen bit survives in exactly one element, ensuring it contributes to the final XOR. If any number in the array contains a specific bit, you can preserve that bit in one position while clearing it from others using repeated AND operations. This means every bit that appears in the array can be made to appear exactly once in the final XOR result. Because XOR of a bit appearing once is 1, the maximum XOR equals the bitwise OR of all numbers. The algorithm simply iterates through the array and accumulates result |= num. This approach relies on understanding properties of Bit Manipulation and how XOR behaves when bits appear an odd number of times.
Approach 2: Try Maintaining Highest Bit (O(n) time, O(1) space)
Another way to reason about the problem is by analyzing bits from highest to lowest. For each bit position, check whether at least one element contains that bit. If it exists anywhere in the array, you can maintain that bit in one number while clearing it from others through AND operations. This guarantees the bit contributes to the final XOR. Effectively, this approach builds the answer bit by bit by scanning the array and checking whether each bit can survive the sequence of operations. The final value becomes the union of all bits seen in the array, which again equals the bitwise OR of all elements. This reasoning approach is helpful when practicing problems involving Array traversal and Math-based bit reasoning.
Recommended for interviews: The XOR‑property insight is what interviewers typically expect. Showing the bit-level reasoning—why any existing bit can be preserved exactly once—demonstrates strong understanding of XOR and AND interactions. A brute-force simulation of operations would be infeasible, so recognizing the OR reduction quickly signals solid bit manipulation skills.
By carefully observing the problem, we notice that the operation simplifies each element of the array such that its bitwise representation tends to be adjusted to involve clearing some of its high bits. Interestingly, for each number, the operation can reduce it but can't increase it. Therefore, the maximum possible XOR is achieved by finding the bitwise OR of all numbers in the array. Subsequently, the maximum XOR becomes equivalent to its OR.
This solution calculates the OR of all elements because OR is a good approximation for the maximum XOR result. Thus, iterating through the array and accumulating the OR in variable 'max_xor' provides the desired result.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1)
Here's an alternative perspective: as you experiment, note that the bend towards using the OR function comes from aiming to maintain the highest significant bit set afterward. For accuracy, you intend to simulate the result such that the most significant bits untouched under AND, deliver the most powerful bit (akin to achieving the pinnacle of XOR).
The solution follows a stringent approach where it iteratively attempts to accumulate bits that weren't part of the currently achieved number using OR, adjusting for conflict scenarios under very particular AND operations.
Time Complexity: O(n)
Space Complexity: O(1)
In one operation, we can update nums[i] to nums[i] AND (nums[i] XOR x). Since x is any non-negative integer, the result of nums[i] \oplus x can be any value. By performing a bitwise AND operation with nums[i], we can change some of the 1 bits in the binary representation of nums[i] to 0.
The problem requires us to find the maximum bitwise XOR sum of all elements in nums. For a binary bit, as long as there is an element in nums with the corresponding binary bit set to 1, the contribution of this binary bit to the maximum bitwise XOR sum is 1. Therefore, the answer is the result of the bitwise OR operation of all elements in nums.
The time complexity is O(n), where n is the length of nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Optimize Using XOR Properties | Time Complexity: O(n), where n is the number of elements in the array. |
| Approach 2: Try Maintaining Highest Bit | Time Complexity: O(n) |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Optimize Using XOR Properties | O(n) | O(1) | Best general solution; uses insight that final XOR equals OR of all elements |
| Maintain Highest Bit | O(n) | O(1) | Useful when reasoning about bit positions individually during interviews |
Leetcode BiWeekly contest 81 - Medium - Maximum XOR After Operations • Prakhar Agrawal • 2,219 views views
Watch 5 more video solutions →Practice Maximum XOR After Operations with our built-in code editor and test cases.
Practice on FleetCode