A function computes the XOR sum of binary numbers. The numbers come from a finite set of "n" constants, whose values are fixed and known (without repeats). The function is passed a subset of these constants and returns the XOR sum.
Question: Given the XOR sum, the value of the n constants, and without knowing how many were combined to produce the output, is it possible to tell which of the "n" constants were input to the function to produce that output? I am aware that if you knew in advance there were only 2 inputs, the solution is trivial: just XOR each of the n constants to the output one at a time to see if you get one of the others. If it does, you have found both. I just can't see how this applies to the general case of 2 to n inputs.
I tried XORing each value to the output one at a time to see if the result was "special" in some way when that value was in the subset of inputs, compared to when it was not. That didn't work.
Any ideas?
There are 2n combinations of values (for each value it is either included or it is not). So this is solvable in O(2n) in the worst case. This is identical to the answer you already noted for n=2. Just keep doing it.
You can optimize this and look at each bit independently. For example, if the first bit is 1, then there must be an odd number of items that have 1 in their first position. Conversely if the first bit is 0, there must be an even number of items. This would allow you to dramatically shrink the search space since only certain combinations are possible. But it's definitely solvable in finite time.
At the extreme end of this optimization, consider the case that there is a 1 in a position, and only one of the values in your set also has a 1 in that position. Clearly that value is included. You can XOR it against the target, and repeat the process.