LovesProgramming's blog

Can this bitwise OR problem be solved ?
By LovesProgramming, history, 6 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 (14)
| Write comment?
»
6 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it
Here is my greedy approach
Example
→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← 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
  • »
    »
    6 years ago, hide # ^ |
    ← 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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
← 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
»
5 years ago, hide # |
 
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