按位和一個數組的子集

Question

任何人都可以提供一個提示如何解決這個問題？

給定一個數組A.是否有數組A的任何子集，其中如果我們做了該子集的所有元素的AND，則輸出應該是2的冪。

我想過要生成一個能量集並解決，但它的複雜性會很差（2^n）。

在此先感謝。

Answer 1

你可以從不同的角度來看它：挑選兩個冪。我們可以生成它嗎？

這個問題很容易回答。從集合中設置與2的冪對應的位的所有項目。計算所有這些的AND。結果必須通過構造找到我們尋找的位，但它可能有或沒有設置任何其他位。如果它還有其他位，那麼選擇其他位（更小 - 你不能選擇任何額外的項目，因爲它們沒有設置目標位）子集也不會工作，它只能有更多錯誤位設置，因爲它將有更少的可能性來解除位。

只要做到這一點所有可能的兩個冪，這只是該集中最大整數的位數。