I have an array of size a = 10⁵ with numbers with sizes of at least 16 bytes.
Now i have to find a subsequence with the xor value equal to k.
The maximum length of this subsequence is n. (1 <= n <= 20)

I tried BruteForce but even with many optimizations it still would take longer than the lifespan of my Computer.
There are many solutions to similar problems online but none of them can be applied here and i was'nt able to find algorithms or methods that could help here.

Does someone know a better solution with a lower time complexity than - if I am right - O(n a^n)?
(Note that I am still in high school so please explain it in a way that i can understand it)

EDIT: subsequence means non-consecutive parts of an array (e.g. ['a', 'c', 'e'] is a subsequence of ['a', 'b', 'c', 'd', 'e'])

CodePudding user response：

After seeing your update, this problem is clearly O(a^n)--exponential time--on the surface. This is among the hardest time complexity classes.

Quite frankly, a program written to tackle this problem in a naive manner will, as you suspect, take an incredibly long time. Not just beyond the life span of your computer, as an n of 20 will have a worst-case result on the order 10^100 operations. Even when adjusted to multiple operations per nanosecond, that's an amount of time so unfathomably large that, assuming I'm not calculating wrong here, would well exceed the heat death of the universe. In other words, you will never solve this problem for a sequence of size 20 on an array of size 100,000 using a naive approach.

And with that said, I don't know if a "quick" solution even exists. This appears, at a glance, to be something called the "k-xor problem". Or rather, if we XOR every element in the array with the value of k, then it should be an identical problem. And the "k-xor problem" appears to have such a large importance in cryptography that there have been continued efforts to create quantum algorithms purely to deal with the time complexity issues of the problem. And these solutions are for smaller values of n, like 3 or 4, not 20. Even non-quantum solutions appear to have solutions on the order of time complexity O(a^(n/2)), which means your worst-case runtime complexity is still going to be executing on the order of 10^50 operations, which is still an unfathomably large number.

You say that you're in high school, and considering there is cutting edge research still being done on improving solutions for this kind of problem, I don't think it's reasonable for you to look into efficiency. I would expect an efficient solution to a problem like this to be asked of graduate-level researchers doing thesis work at a minimum, not of a high school student.

Unless there are important details you're leaving out or misunderstanding that could potentially reduce the problem complexity significantly, there's just no way you're going to write an efficient solution. Period.

In short, I would take that as permission to simply ignore the size of the problem and just write a solution that can work on smaller values of a and n. If your teacher somehow knows of a fast algorithm, then maybe they should submit a research paper.