Get started

Maximum XOR After Operations — Medium Problem & Solution

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).

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 <= 100000
  • 0 <= nums[i] <= 100000000

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

  1. 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue