按位和一个数组的子集

Question

任何人都可以提供一个提示如何解决这个问题？

给定一个数组A.是否有数组A的任何子集，其中如果我们做了该子集的所有元素的AND，则输出应该是2的幂。

我想过要生成一个能量集并解决，但它的复杂性会很差（2^n）。

在此先感谢。

Answer 1

你可以从不同的角度来看它：挑选两个幂。我们可以生成它吗？

这个问题很容易回答。从集合中设置与2的幂对应的位的所有项目。计算所有这些的AND。结果必须通过构造找到我们寻找的位，但它可能有或没有设置任何其他位。如果它还有其他位，那么选择其他位（更小 - 你不能选择任何额外的项目，因为它们没有设置目标位）子集也不会工作，它只能有更多错误位设置，因为它将有更少的可能性来解除位。

只要做到这一点所有可能的两个幂，这只是该集中最大整数的位数。