Given an array of elements Ai (<=1e9) of length N (<=1e5), and another array named 'operands' of size K (<=4), You can do the following operations as many times as desired: Select any element in original array and XOR it with any element in 'operands' array. **Minimize the Maximum difference between any pairs of the array**.

it's a little "sus" on your avatar

I don't understand what does K do here?

Updated the statement, let me know if the problem is intuitive.

One idea I could think of immediately:

Pivot $$$A_1$$$. Perform $$$16$$$ different cases, with each case having $$$A_1$$$ xor-ing with every element in a subset of operand array (empty subset means keeping $$$A_1$$$ as-is), we'll call the new value $$$A_1'$$$.

For each case, try to make other elements as close to $$$A_1'$$$ as possible. As one can guess, any other element also has $$$16$$$ possibilities each.

This solution has $$$\mathcal{O}(n \cdot 4^k)$$$ complexity.

Considering whatever you explained, consider this: How about for every subset of operands, we XOR the subset XOR value with each element of the array, sort those 16 possibilities and store it in a matrix[N][16]. Now the problem statement just changed to selecting one element from each row and maintaining minimum difference between the maximum chosen and the minimum chosen value. Isn't this a famous question we've seen somewhere?

Yes, here we can enumerate the minimum and then use O(2^k·n) to solve. When an element no longer qualifies for the minimum value, we replace it with an element in the array that is just larger than it.

Making each element as close to a1 as possible doesn't guarantee the greatest gap is the least, right?

For example, a2 = (a1-1 or a1+5). a3 = (a1+5 or a1+7).

You would choose "a1-1" versus "a1+5" with a difference of 6.

The correct choice is "a1+5" and "a1+5", the difference is 5.

And you can't handle the case if you have two closest values at the same time.

I see. My bad there.

Nice pic bro

There are in total 16 possible masks for the each element of the array. Generate those 16 masks and XOR each element of the array with it and sort all values and store it in a N x 16 matrix. Now you have a matrix with each row sorted, apply priority queue and keep N-pointers for each row and iterate through all elements column wise. Here's the code:

We have 16 possibilities we can do on each array value, for each apply it on A1, let us note it as A1'. Now we center all others element around A1', by doing binary search, let's find the minimum k, such as A1' — k <= Ai' <= A1 + k, and the answer will be minimum of maxAi' — minAi' among all possibility.

The complexity is O(nlogn). Each step of the binary will be O(n) because for each i, we will verify only among 16 cases, if at least one is in the interval.