Maximum XOR After Operations

Medium
726.

Maximum XOR After Operations

Maximum XOR After Operations is a medium coding problem on arrays, bit manipulation and brainteaser, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumXOR = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Maximum XOR After Operations

  1. Hint 1

    Work out what the operation can actually do to a single element.

  2. Hint 2

    nums[i] AND (nums[i] XOR x) can clear any subset of the bits that nums[i] already has — and can never set a new one.

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

  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

Java

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