So, basically this problem can be considered as a simpler version of https://codeforces.me/blog/entry/74836 . I was wondering what can be the approach if we fix the size of the subset.
Given an array of size N , find the maximum bitwise or of elements in a subset of size K.
What can be the best(time complexity wise) possible approach for this problem apart from this ? Can anyone please help?
UPD: I had initially written Xor everywhere instead of Or. Sorry.
Clarification- Is the subset size fixed = k?
Yes.
If K is a part of the input to the problem, then this is not a simpler version of the task "given an array of size N, find the maximum bitwise xor of any subset of elements", as you could:
Now, you can easily see that there exists a solution with XOR = $$$x$$$ to the new problem (array of size $$$N'$$$, we want to find a subset of size $$$K'$$$) if and only if there exists a solution with XOR = $$$x$$$ to the original problem. So, in some sense, your problem is at least as hard as the original problem.
Shit, I realized I wrote XOR by mistake. Sorry for this extremely dumb mistake. I intended to write OR.
Anyway, Thanks a lot for your insight.
Oh, okay. So I believe my construction still works? And if the original problem is NP-complete (assuming the numbers can be arbitrarily large, and not bounded by something like 1e5), then your problem should be NP-complete as well.
Yeah, I understood your point. For arbitrarily large numbers your points seem valid.
Annoying purist here: I don't see how the maximisation problem is in NP. What you probably meant to say was NP-hard.
If K is not fixed, we can just use Gaussian Elimination as described in this article, and find the maximum Xor in O(n*log(A_max)).
P.S- Author just changed xor to or...This is one of the solution for xor.
Well, apparently you're right. :D
So it's an interesting question if we can solve the OP's problem with XOR instead of OR. It's weird because it's "a thing I should probably know about", but somehow I don't.