pritishn's blog

Need some help in a OR problem.
By pritishn, 4 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Clarification- Is the subset size fixed = k?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +45 Vote: I do not like it

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:

  1. Take any input to the problem without any fixed $$$K$$$; say, it contains $$$N$$$ integers.
  2. Pad the array with $$$N$$$ zeroes (so that the new array has $$$N' = 2N$$$ integers).
  3. Set $$$K' = N$$$ (that is, $$$K' = \frac12 N'$$$).
  4. We get an instance of your problem, with an array of $$$N'$$$ integers, where we want to maximize the xor of elements in a subset of size $$$K'$$$.

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I understood your point. For arbitrarily large numbers your points seem valid.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Annoying purist here: I don't see how the maximisation problem is in NP. What you probably meant to say was NP-hard.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      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.

      → Reply