LovesProgramming's blog

Can this bitwise OR problem be solved ?
By LovesProgramming, history, 5 years ago, In English

Problem : — Given an array ,find the size of the smallest subset with maximum Bitwise OR .

Constraints : — 1<=N<=100000 ; 1<=A[I]<=1000000000

I found an article which solves this problem : https://www.geeksforgeeks.org/size-of-the-smallest-subset-with-maximum-bitwise-or/

But this solution[greedy] fails on the test-case : {56,33,7}

So is there any real solution for this problem ?

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

Comments Comments (15)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
Here is my greedy approach
Example
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    Here is my another approach

    Oh sorry, I dont see that you have a better solution ;-;

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

    hi, your approach is correct but, in the loop from 64 to 0 -> if we are at a position 'p', then we have to consider every integer in the array who has 'p'th position set. We cant just consider the one which comes first in the sorted vector. As it might have a lower bit as 0 but in other int (which is lower in the sorted vector) that position might be set. for eq-> 7 91 29 58 45 51 74 70 **->This is regarding the greedy approach above.

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

The problem is equivalent to set cover, with univerise size log(max), and number of subsets simply N. So unless P = NP, your solution will be either exponential in N (just no...), or exponential in log(max), which could be more promising but seems difficult.

It's nothing new that GFG spreads around wrong solutions.

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

    Is it NP hard or can be solved in Polinomial Time? Because same question asked in Google online Test 2 days before in hackerearth...

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

      We can solve it using bitwise convolution
      This is well tested code(mostly)
      Pastebin link
      time complexity is n logn^2, we can optimise it using binary lifting to n logn log logn
      Edit : here n = 2^20

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

        Can u explain what is inverse and transform?

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

        The above solution is not even passing sample case given in the above post.

        3

        56 33 7

        Answer for this should be 2.

        But your brute force and actual answer both giving 3. Your tested your approach with wrong brute force.

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

          what ??? It is giving correct answer as 2
          I guess you forget to comment cin >> x;

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

is this approach is correct?


1.First get total sum from the array using bit wise operator
2.After that sort the array
3.initialise a count = 0 variable and temp = arr[0]
4.loop through the sorted array(1..n):
       1.temp = temp|array[i]
       2.if(temp==sum):
           1.print(count)
           2.break
       3.else operate the next element to temp
5.end
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you sort the array, Are you not loosing the order of elements?

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

      Bro, we need subset not subarray, so order doesn't matter :)

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

A similar problem. XORSUB. just consider K = 0. and one possible solution for this is using Gaussian Elimination for XOR Maximization this will also satisfy the above constraints

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we do this greedily by first storing the logical or of all numbers and then sorting the elements in decreasing order according to their popcount (in order decreasing number of set bits). and then if a[i]>maxOr -> i++ else we take or with it and push it into a set, after our number has become equal to the maxOR, we stop and return the size of set. Is this fine?

→ Reply