Skip to content

2317. Maximum XOR After Operations

Description

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

Solutions

Solution 1: Bit Manipulation

In one operation, we can update \(\textit{nums}[i]\) to \(\textit{nums}[i] \text{ AND } (\textit{nums}[i] \text{ XOR } x)\). Since \(x\) is any non-negative integer, the result of \(\textit{nums}[i] \oplus x\) can be any value. By performing a bitwise AND operation with \(\textit{nums}[i]\), we can change some of the \(1\) bits in the binary representation of \(\textit{nums}[i]\) to \(0\).

The problem requires us to find the maximum bitwise XOR sum of all elements in \(\textit{nums}\). For a binary bit, as long as there is an element in \(\textit{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 \(\textit{nums}\).

The time complexity is \(O(n)\), where \(n\) is the length of \(\textit{nums}\). The space complexity is \(O(1)\).

1
2
3
class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        return reduce(or_, nums)

1
2
3
4
5
6
7
8
9
class Solution {
    public int maximumXOR(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            ans |= x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int maximumXOR(vector<int>& nums) {
        int ans = 0;
        for (int& x : nums) {
            ans |= x;
        }
        return ans;
    }
};

1
2
3
4
5
6
func maximumXOR(nums []int) (ans int) {
    for _, x := range nums {
        ans |= x
    }
    return
}

1
2
3
4
5
6
7
function maximumXOR(nums: number[]): number {
    let ans = 0;
    for (const x of nums) {
        ans |= x;
    }
    return ans;
}

Comments