{x}
blog image

Maximum XOR After Operations

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

Solution Explanation

The problem asks for the maximum possible bitwise XOR of all elements in the input array nums after applying a specific operation any number of times. The operation involves choosing a non-negative integer x and an index i, and updating nums[i] to nums[i] AND (nums[i] XOR x).

However, a crucial observation simplifies the problem significantly:

The expression nums[i] AND (nums[i] XOR x) can be simplified. Let's denote nums[i] as a. The operation becomes a AND (a XOR x). Using bit manipulation properties, we know that a AND (a XOR x) is equivalent to setting some bits of a to 0 (the bits where x has a 1). It cannot set any bits to 1 that weren't already present in a.

Therefore, no matter what operation is performed, we can never create a 1 bit where there wasn't already a 1 in at least one element of the original array. The maximum XOR value is achievable by simply performing a bitwise OR operation on all numbers in the input array. This OR operation finds the set of bits that are present in at least one of the numbers. This set of bits represents the maximum possible contribution of each bit position to the final XOR sum.

Algorithm

  1. Initialize ans to 0. This variable will store the result (the maximum XOR).
  2. Iterate through the nums array.
  3. In each iteration, perform a bitwise OR operation (|=) between ans and the current element x. This ensures that all bits present in any of the numbers in nums are set in ans.
  4. Return ans.

Time and Space Complexity

  • Time Complexity: O(N), where N is the length of the nums array. We iterate through the array once.
  • Space Complexity: O(1). We use only a constant amount of extra space.

Code Implementation (Python)

from functools import reduce
import operator
 
class Solution:
    def maximumXOR(self, nums: List[int]) -> int:
        return reduce(operator.or_, nums)

This Python code uses the reduce function from the functools module and the operator.or_ function to efficiently perform the bitwise OR operation on all elements of the list. It's equivalent to the iterative approach but more concise.

Code Implementation (Other Languages)

The other language implementations (Java, C++, Go, TypeScript) follow the same basic algorithm; they iterate through the array and perform a bitwise OR operation in each iteration. The only difference lies in the syntax of each language. All of them have the same O(N) time complexity and O(1) space complexity.