Maximum XOR After Operations - Video Solutions
Leetcode BiWeekly contest 81 - Medium - Maximum XOR After Operations
Maximum XOR After Operations - Video Solution
Watch 6 video solutions for Maximum XOR After Operations , a medium level problem involving Array, Math, Bit Manipulation. This walkthrough by Prakhar Agrawal has 2,232 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
Approach Overview
Problem 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.
Complexity Analysis
| 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 |