Java.Algo.2275. Largest Combination With Bitwise AND Greater Than Zero

https://leetcode.com/problems/largest-combination-with-bitwise-and-greater-than-zero/description/

    public int largestCombination(int[] candidates) {
          if (candidates.length == 1) {
              return 1;
          }

          int maxCountBits = 24;
          int max = 0;
          for (int i = 0; i < maxCountBits; i++) {
              int count = 0;
              for (int c : candidates) {
                  if ((c & (1 << i)) != 0) {
                      count++;
                  }
              }
              max = Math.max(max, count);
              if (max == candidates.length) {
                  return max;
              }
          }

          return max;
    }

🧠 Key Insight:

For the bitwise AND of multiple numbers to be greater than 0, they must all share at least one bit set to 1.
In other words, there must be at least one bit position where all numbers in the subset have a 1.

---

💡 Efficient Strategy:

Instead of checking all possible combinations (which would be too slow), we flip the problem and ask:

For each bit position (from 0 to 23), how many numbers in the array have a 1 at that bit?

---

Why this works:

• If k numbers have bit i set to 1, we can form a group of size k whose AND will still keep that bit set.
• The AND of those k numbers will be greater than 0 because bit i will survive.
• So we just need to find the bit position that appears in the most numbers.

---

🧮 Steps:

1. Loop through all bit positions (0 to 23) — 24 bits because numbers are ≤ 10⁷.
2. For each bit position:
   • Count how many numbers have that bit set using (c >> i) & 1.
3. Keep track of the maximum count found across all bit positions.

---

🏁 Result:

That maximum count is the size of the largest subset with AND > 0.