CODEWITHSUNDEEP
arrayssetbit-manipulationbitwise-operators
JP King
JP King

Reputation: 13

Bitwise and of subsets of an array

Can anyone give a hint how to approach this problem?

Given an array A. Is there any subset of array A in which if we do AND of all elements of that subset then output should be in power of two.

I've thought of generating a power-set and solving but it will have a very bad complexity (2^n).

Thanks in Advance.

Upvotes: 1

Views: 1143

Answers (1)

user555045
user555045

Reputation: 64904

You can look at it from a different perspective: pick a power of two. Can we generate it?

This question is easy to answer. Take all items from the set in which the bit corresponding to the power of two is set. Calculate the AND of all of those. The result must by construction have the bit that we looked for set, but it may or may not have any other bits set. If it has other bits as well, then choosing some other (smaller - you can't choose any extra items because they don't have the target bit set) subset wouldn't work either, it could only have more wrong bits set because it would have fewer possibilities to unset bits.

Just do that for all possible powers of two, that's only as many as there are bits in the largest integer in the set.

Upvotes: 3

Related Questions