Largest AND Combination LeetCode 2275

LeetCode 2275 — Largest Combination with Bitwise AND Greater Than Zero — gives you an array of positive integers called candidates and asks you to find the size of the largest combination (subset) such that the bitwise AND of all chosen numbers is strictly greater than zero.

A combination here means any subset of the candidates array — order does not matter and you may choose any number of elements from 0 to the full length. The constraint is that candidates[i] can be up to 10^7, which fits within 24 bits since 2^24 = 16,777,216 > 10^7.

The result is always at least 1 because any single positive integer has AND equal to itself, which is greater than zero. The challenge is to find the largest such group efficiently without enumerating all 2^n subsets.

The bitwise AND of a set of numbers is greater than zero if and only if at least one bit position has a 1 in every chosen number. This is because AND produces a 1 at position j only when all operands have a 1 at position j. If any number is missing the bit, AND clears it to 0.

This means that to maximize the subset size, you want to find the bit position j where the most candidates have a 1. Any candidate with bit j set can be included in the combination, and all such candidates will have an AND with at least bit j set — guaranteeing the result is non-zero.

There is no benefit to mixing candidates from different bit positions because adding a candidate that does not have bit j set will clear bit j from the AND, potentially making the AND zero. The optimal strategy is always to commit to a single bit position and collect all numbers that share it.

The algorithm loops over each of the 24 bit positions (indices 0 through 23) and counts how many candidates have that bit set. A number x has bit j set when (x >> j) & 1 equals 1. You accumulate the count across all candidates for each bit position.

After processing all 24 bit positions you have 24 counts. The answer is the maximum of these counts. The total work is 24 × n operations, which is O(n) since 24 is a constant. Extra space is O(1) — you only need the running maximum.

Candidates can be up to 10^7, which is less than 2^24 = 16,777,216. This means bits at position 24 and above are always zero for every candidate, so checking 24 positions is both necessary and sufficient.

If k numbers all have bit j set, then taking all k of them yields a bitwise AND that has at least bit j set, so the AND is at least 2^j > 0. This proves that k is a valid combination size. No larger group using bit j is possible because we already took every candidate with that bit.

Can we do better by using multiple bit positions? No. Suppose we try to combine candidates that share bit j with candidates that share bit m (j ≠ m). Any candidate in the group must have both bits set to keep the AND non-zero at both positions. But the count of numbers with both bits set is at most min(count_j, count_m), which is no larger than max(count_j, count_m). Committing to a single bit always gives an equal or larger group.

The optimality argument is clean: each bit position defines an independent "column" of the binary representation. The best strategy is to pick the column with the most 1s and select every number in that column.

Consider candidates = [16, 17, 71, 62, 12, 24, 14]. In binary: 16 = 0010000, 17 = 0010001, 71 = 1000111, 62 = 0111110, 12 = 0001100, 24 = 0011000, 14 = 0001110. Check bit 0 (value 1): numbers with bit 0 set are 17 (…1), 71 (…1) — count = 2. Check bit 1 (value 2): 71 (…11), 62 (…10), 14 (…10) — count = 3.

Check bit 2 (value 4): 71 (1000111), 62 (0111110), 12 (0001100), 14 (0001110) — count = 4. Check bit 3 (value 8): 71, 62, 12, 24, 14 — five numbers have bit 3 set. Let us verify: 71 & 8 = 8 yes; 62 & 8 = 8 yes; 12 & 8 = 8 yes; 24 & 8 = 8 yes; 14 & 8 = 8 yes; 16 & 8 = 0 no; 17 & 8 = 0 no. Count at bit 3 = 5.

Check bit 4 (value 16): 16, 17, 71 have bit 4 set — count = 3. Check bit 5 (value 32): 62 (0111110) and 71 (1000111): 62 & 32 = 32 yes, 71 & 32 = 0 no. Only 62 → count = 1. The maximum count across all positions is 5 at bit 3, so the answer is 5.

Python solution: def largestCombination(candidates): return max(sum((x >> j) & 1 for x in candidates) for j in range(24)). The outer generator iterates over 24 bit positions; the inner sum counts candidates with that bit set; max picks the best position. Time O(24n) = O(n), space O(1).

Java solution: public int largestCombination(int[] candidates) { int ans = 0; for (int j = 0; j < 24; j++) { int count = 0; for (int x : candidates) if (((x >> j) & 1) == 1) count++; ans = Math.max(ans, count); } return ans; }. The two nested loops give O(24n) time and O(1) space.

Both implementations are cache-friendly and straightforward to understand. The Python one-liner uses generator expressions to avoid allocating intermediate lists. The Java version is explicit about the bit extraction and comparison, which makes it easy to optimize with SIMD or bit-parallel tricks if needed.

LeetCode 2275 belongs to the bit-column counting family. Bitwise AND of Numbers in a Range (LeetCode 201) also reasons about AND over a set of numbers — it finds the common prefix of the binary representations of left and right. The technique of isolating individual bit positions appears in both problems.

Minimum Number of Flips to Make OR Equal (LeetCode 1318) and Counting Bits (LeetCode 338) also involve per-bit analysis. In Counting Bits you compute the number of set bits for every integer from 0 to n; in LeetCode 1318 you check each bit of three numbers to determine flips needed. The column-wise bit perspective — treating each bit independently across all numbers — is the common thread.

The broader bit manipulation toolkit includes: popcount (number of set bits), XOR tricks for finding a unique element, two's complement for sign handling, and bitmask DP for subset enumeration. Mastering column-wise bit counting as demonstrated by LeetCode 2275 is a key building block for the harder problems in this category.