# Maximum XOR After Operations 
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-xor-after-operations)
Canonical: https://scaleengineer.com/dsa/problems/maximum-xor-after-operations
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## Problem
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 <= 105`
* `0 <= nums[i] <= 108`

# Approaches
## Brute-Force with Submasks (Time Limit Exceeded)
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.
**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`.
**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.
### Explanation
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)`.
```java
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);
    }
}
```
### Algorithm
*   Define a recursive function `solve(index, currentXOR)`.
*   **Base Case:** If `index` equals the length of `nums`, update the global maximum XOR value with `currentXOR` and return.
*   **Recursive Step:** For the number `nums[index]`, iterate through all its submasks `s`. For each `s`, recursively call `solve(index + 1, currentXOR ^ s)`.

## Bitwise OR Insight
This highly efficient approach stems from a key insight into the properties of the given operation and the goal of maximizing a bitwise XOR sum. The core idea is to analyze the problem on a bit-by-bit basis.
**Time:** O(N), where N is the number of elements in `nums`. We perform a single pass through the array. · **Space:** O(1). We only use a single integer variable for storage, regardless of the input size.
**Pros:** Optimal time and space complexity.; The solution is simple and elegant.
**Cons:** The solution relies on a non-obvious insight about the bitwise operations, which might not be easy to derive under pressure.
### Explanation
First, let's analyze the operation: `new_val = val AND (val XOR x)`.
Let's consider the k-th bit. If the k-th bit of `val` is 0, the k-th bit of `new_val` will be `0 AND (0 XOR x_k) = 0`. This means a 0-bit can never be turned into a 1-bit.
If the k-th bit of `val` is 1, the k-th bit of `new_val` will be `1 AND (1 XOR x_k)`. By choosing `x_k=0`, the result is `1 AND 1 = 1`. By choosing `x_k=1`, the result is `1 AND 0 = 0`. This means we can freely change any 1-bit to a 0-bit, or keep it as a 1.
In summary, for any number `nums[i]`, we can change it to any of its submasks (i.e., turn any of its set bits off).
Our goal is to maximize the final XOR sum `S = nums[0]' XOR ... XOR nums[n-1]'`. To maximize `S`, we want to set as many of its most significant bits to 1 as possible.
Consider the k-th bit of the result, `S_k`. Can we make `S_k = 1`? This requires an odd number of `nums[i]'_k` to be 1. A bit `nums[i]'_k` can be 1 only if the original `nums[i]_k` was 1.
If for a given bit `k`, at least one number `nums[j]` has its k-th bit set (`nums[j]_k = 1`), we can achieve `S_k = 1`. We do this by choosing `nums[j]'` to have its k-th bit as 1, and for all other numbers `nums[i]'` (where `i != j`), we choose their k-th bit to be 0 (which is always possible). The XOR sum of these k-th bits will be 1.
If for a given bit `k`, no number `nums[i]` has its k-th bit set, then `nums[i]_k` is 0 for all `i`. Consequently, `nums[i]'_k` must also be 0 for all `i`, and `S_k` will be 0.
Therefore, the k-th bit of the maximum possible XOR sum is 1 if and only if the k-th bit is 1 in at least one of the original numbers. This is precisely the definition of the bitwise OR operation.
The maximum XOR sum is simply the bitwise OR of all elements in the `nums` array.
The algorithm is to iterate through the array and compute the cumulative bitwise OR.
```java
class Solution {
    public int maximumXOR(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result |= num;
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an integer variable `res` to 0.
*   Iterate through each number `num` in the input array `nums`.
*   For each `num`, update `res` by performing a bitwise OR operation: `res = res | num`.
*   After the loop finishes, `res` will hold the bitwise OR of all elements.
*   Return `res`.

# Solutions
### Java

```java
class Solution {
public
  int maximumXOR(int[] nums) {
    int ans = 0;
    for (int x : nums) {
      ans |= x;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int maximumXOR ( vector < int >& nums ) { int ans = 0 ; for ( int & x : nums ) { ans |= x ; } return ans ; } };
```

### Python

```python
class Solution:
    def maximumXOR(self, nums: List[int]) -> int: return reduce(or_, nums)

```