Can this bitwise OR problem be solved ?

Блог пользователя LovesProgramming

Автор LovesProgramming, история, 6 лет назад, По-английски

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 ?

#bitwise, #bitwiseor

LovesProgramming
6 лет назад
18

Комментарии (14)

Показать архивные | Написать комментарий?

SPyofgame

6 лет назад, скрыть # |

← Rev. 3 →

Here is my greedy approach

-- Transform all to binary form
-- Sort them from left to right (high to low)

-- Make (mark) variable empty (00000000)
-- Make a loop for binary position (p) = (highest -> lowest)
---- Find a number whose binary form at (p)
------ If exist let (mark) |= maximum number set at (p)
------ else continue

Example

n = 5
toBin[0] = 00001101
toBin[1] = 00000011
toBin[2] = 00000100
toBin[3] = 00001010
toBin[4] = 00000001

Sort
toBin[0] = 00001101
toBin[1] = 00001010
toBin[2] = 00000100
toBin[3] = 00000011
toBin[4] = 00000001

(P, mark, selected)
7 : 0_______ | X
6 : 00______ | X
5 : 000_____ | X
4 : 0000____ | X
3 : 00001101 | 00001101
2 : 00001101 | 00001101
1 : 00001111 | 00001101 00000011
0 : 00001111 | 00001101 00000011

Result:
2
toDec(00001101) toDec(000000011)

→ Ответить

SPyofgame

6 лет назад, скрыть # ^ |

← Rev. 3 →

Here is my another approach

-- Get array (Array)
-- Transform all to binary form

-- Let (mark) = 00000000
-- Create (result) vector
-- For (bit) = the highest possible set bit -> the lowest
---- Create 2 new vector
---- For each element (x) E (Array)
------ If position (p) in (x) is set
------ True:  Push them to (first) vector
------ False: Push them to (second) vector
---- Do something

-- output << result.size
-- for each element (x) E (result)
---- output << x

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

→ Ответить

divit.singhal2020

6 лет назад, скрыть # ^ |

← Rev. 5 →

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.

→ Ответить

Noam527

6 лет назад, скрыть # |

+19

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.

→ Ответить

vrkorat211

6 лет назад, скрыть # ^ |

+15

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

→ Ответить

navneet.h

6 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

vrkorat211

6 лет назад, скрыть # ^ |

Can u explain what is inverse and transform?

→ Ответить

navneet.h

6 лет назад, скрыть # ^ |

see this

→ Ответить

rahul_107

6 лет назад, скрыть # ^ |

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

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.

→ Ответить

navneet.h

6 лет назад, скрыть # ^ |

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

→ Ответить

debomastet

6 лет назад, скрыть # |

← Rev. 2 →

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

→ Ответить

tejas

6 лет назад, скрыть # ^ |

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

→ Ответить

vrkorat211

6 лет назад, скрыть # ^ |

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

→ Ответить

rahul_107

5 лет назад, скрыть # |

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

→ Ответить