Bitwise and of subsets of an array

Question

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.

user555045 · Accepted Answer · 2015-06-06 13:11:35Z

3

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.

answered Jun 6, 2015 at 13:11

user555045

65.8k6 gold badges95 silver badges180 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Bitwise and of subsets of an array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related