Maximum XOR After Operations — Problem & Solution
Maximum XOR After Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum XOR After Operations is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Brainteaser
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You may repeat this operation any number of times: pick an index i and any non-negative x, and replace nums[i] with nums[i] AND (nums[i] XOR x).
Return the maximum possible XOR of the whole array afterwards.
Example 1
Input: nums = [3,2,4,6]
Output: 7
Explanation: Bits 0, 1 and 2 each appear somewhere, and the operations can leave each of them in an odd number of elements — giving 7.
Example 2
Input: nums = [1,2,3,9,2]
Output: 11
Explanation: The OR of the array is 11.
Example 3
Input: nums = [8]
Output: 8
Constraints
1 <= nums.length <= 1000000 <= nums[i] <= 100000000
Hints for Maximum XOR After Operations
Hint 1
Work out what the operation can actually do to a single element.
Hint 2
nums[i] AND (nums[i] XOR x)can clear any subset of the bits thatnums[i]already has — and can never set a new one.Hint 3
So each bit that appears anywhere can be made to appear an odd number of times, and no other bit can appear at all.
How to solve Maximum XOR After Operations
The operation is exactly 'clear any subset of this element's set bits'. So the reachable XOR values are precisely those whose set bits are a subset of the array's OR — and the OR itself is reachable, so it is the maximum.
Approach
- Return the bitwise OR of every element.
Why it works
For a bit b set in the OR, some element has it; clear b from every other element that has it, leaving exactly one, so the XOR has b set. A bit absent from every element can never be created, since the operation only clears. Doing this for all bits simultaneously is consistent because the choices per bit are independent.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Trying to simulate operations is hopeless — the insight is that the operation is a masked clear.
- XOR-ing the array gives a value that is usually far below the achievable maximum.
Reference solution
Python
from typing import List
def maximumXOR(nums: List[int]) -> int:
out = 0
for x in nums:
out |= x
return outJava
public static int maximumXOR(int[] nums) {
int out = 0;
for (int x : nums) out |= x;
return out;
}C++
int maximumXOR(vector<int>& nums) {
int out = 0;
for (int x : nums) out |= x;
return out;
}JavaScript
var maximumXOR = function(nums) {
var out = 0;
for (var i = 0; i < nums.length; i++) out |= nums[i];
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation