Strongest XOR Blend

HardBit Manipulation

Problem

A cipher designer has a pool of key fragments fragments. A blend is the XOR of any subset of the fragments (each used at most once); the empty subset blends to 0.

Return the largest blend value that can be produced.

Example 1

Input:
fragments = [3, 10, 5]
Output:
15

10 XOR 5 = 1010 XOR 0101 = 1111.

Example 2

Input:
fragments = [7]
Output:
7

Example 3

Input:
fragments = [4, 4, 4]
Output:
4

Constraints

  • 1 ≤ fragments.length ≤ 10^5
  • 0 ≤ fragments[i] < 2^31

Hint

Show the first hint

There are 2^n subsets, far too many. What structure does the set of all reachable blends have?

Walkthrough

How to approach it

01Clarify before coding

  • Is the empty subset allowed? Yes, so the answer is at least 0.
  • Can fragments repeat? Yes; duplicates add nothing new.
  • Do we need the subset itself? No, only the maximum value.

02Brute force

Enumerate every subset and XOR its members, or keep a set of all reachable values and extend it fragment by fragment.

Cost: O(2^n) subsets, or up to 2^31 reachable values in the set: both infeasible.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.