🔗 🟡 2275. Largest Combination With Bitwise AND Greater Than Zero

Problem Statement

題目簡述

給定一個正整數陣列，求最大的子集大小，使得該子集中所有元素的位元 AND 大於 0。

Constraints

約束條件

  • 1≤n≤1051 \le n \le 10^5，其中 nn 為陣列長度
  • 1≤candidates[i]≤1071 \le \text{candidates}[i] \le 10^7

思路：枚舉每個位元

關鍵觀察

若某個位元在所有選中數字中都是 1，則 AND 結果在該位元上必定為 1。因此，只要存在某個位元使得足夠多的數字在該位元上為 1，就能構造出一個合法組合。

題目要求選出一個子集，使得所有元素的位元 AND 大於 0。AND 結果大於 0，意味著其二進位表示中至少有一個位元是 1。而一個位元在 AND 結果中為 1，若且唯若該位元在所有被選中的數字中都是 1。

因此，問題等價於：對於每個位元位置 bb，統計有多少個數字在該位元上是 1，取所有位元中的最大值。因為只要把這些數字全部選入組合，它們在該位元上的 AND 就是 1，整個組合的 AND 必定大於 0。

為什麼只看單一位元就夠了？

設想我們選了某個位元 bb 上為 1 的所有數字。這些數字的 AND 在第 bb 位一定是 1（因為每個數字的該位都是 1），因此 AND 結果 ≥2b>0\ge 2^b > 0。這保證了合法性。而任何合法的組合，其 AND 結果的某個位元必定為 1，該組合的大小不可能超過「該位元上為 1 的數字總數」。因此最大值必在某個單一位元的計數中取得。

方法一：先枚舉位元，再統計數字

最直接的做法：外層枚舉位元 b∈[0,23]b \in [0, 23]（因為 107<22410^7 < 2^{24}），內層遍歷所有數字，統計第 bb 位為 1 的數字個數，取所有位元中的最大值。

複雜度分析

  • 時間複雜度：O(nlog⁡U)\mathcal{O}(n \log U)，其中 U=max⁡(candidates)U = \max(\text{candidates})，log⁡U≤24\log U \le 24
  • 空間複雜度：O(1)\mathcal{O}(1)

方法二：先枚舉數字，再用 lowbit 提取位元

另一種思路是反過來：遍歷每個數字，對於每個數字，用 lowbit 逐個提取其中為 1 的位元，並在對應的計數器上加一。最後取所有計數器的最大值。

lowbit 技巧

x & -x 可以取出 xx 的最低位的 1 所代表的值。重複減去 lowbit 直到 xx 變為 0，就能遍歷一個數字中所有為 1 的位元，而不需要檢查所有 24 個位元。

這種做法在數字中 1 的數量較少時更高效（例如數字普遍較小或較稀疏時），但最壞情況（所有位元都是 1）下與方法一等價。

複雜度分析

  • 時間複雜度：O(nlog⁡U)\mathcal{O}(n \log U)，最壞情況下每個數字需要檢查 log⁡U\log U 個位元
  • 空間複雜度：O(log⁡U)\mathcal{O}(\log U)，需要一個大小為 24 的計數陣列
題型總結

核心技巧是位元分解 + 計數。遇到位元 AND/OR 相關問題時，優先考慮逐位元獨立處理——位元運算在每個位元上是獨立的。將「整個數字的 AND > 0」轉化為「存在某個位元在所有選中數字中都是 1」，就從子集組合問題退化為簡單的逐位元計數。

Code

方法一：先枚舉位元，再統計數字

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        # return max(sum((x >> b) & 1 for x in candidates) for b in range(24))
        ans = 0
        for b in range(24):
            cur = 0
            for x in candidates:
                if (x >> b) & 1:
                    cur += 1
            ans = max(ans, cur)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        int ans = 0, cur = 0;
        for (int b = 0; b < 24; b++) {
            cur = 0;
            for (int x : candidates) {
                if ((x >> b) & 1) cur++;
            }
            ans = max(ans, cur);
        }
        return ans;
    }
};

方法二：先枚舉數字，再用 lowbit 提取位元

1
2
3
4
5
6
7
8
9
class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        cnt = [0] * 24
        for x in candidates:
            while x:
                lb = x & -x
                x -= lb
                cnt[lb.bit_length() - 1] += 1
        return max(cnt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        vector<int> cnt(24);
        for (int x : candidates) {
            while (x) {
                int lb = x & -x;
                x -= lb;
                cnt[__builtin_ctz(lb)]++;
            }
        }
        return *max_element(cnt.begin(), cnt.end());
    }
};