# Largest Combination With Bitwise AND Greater Than Zero
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-combination-with-bitwise-and-greater-than-zero)
Canonical: https://scaleengineer.com/dsa/problems/largest-combination-with-bitwise-and-greater-than-zero
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Jump Trading](https://scaleengineer.com/companies/jump-trading)
---
## Problem
The **bitwise AND** of an array `nums` is the bitwise AND of all integers in `nums`.

* For example, for `nums = [1, 5, 3]`, the bitwise AND is equal to `1 & 5 & 3 = 1`.
* Also, for `nums = [7]`, the bitwise AND is `7`.

You are given an array of positive integers `candidates`. Compute the **bitwise AND** for all possible **combinations** of elements in the `candidates` array.

Return _the size of the **largest** combination of_ `candidates` _with a bitwise AND **greater** than_ `0`.

**Example 1:**

**Input:** candidates = [16,17,71,62,12,24,14]
**Output:** 4
**Explanation:** The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

**Example 2:**

**Input:** candidates = [8,8]
**Output:** 2
**Explanation:** The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.

**Constraints:**

* `1 <= candidates.length <= 105`
* `1 <= candidates[i] <= 107`

# Approaches
## Brute-Force by Generating All Subsequences
This approach involves generating every possible non-empty combination (subsequence) of the `candidates` array. For each combination, we calculate the bitwise AND of its elements. If the result is greater than zero, we compare its size with the largest size found so far and update it if necessary.
**Time:** O(N * 2^N), where `N` is the number of candidates. There are `2^N` subsequences, and for each, we iterate up to `N` elements to calculate the AND. This is computationally infeasible for the given constraints. · **Space:** O(1). The iterative bitmask approach uses constant extra space.
**Pros:** Conceptually simple and directly follows the problem definition.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest input sizes (e.g., N > 20).
### Explanation
The most straightforward way to solve the problem is to simulate the process described. We can generate all possible combinations of numbers from the `candidates` array, calculate their bitwise AND, and if the result is positive, we note the size of that combination. We keep track of the maximum size found across all combinations.

Generating all combinations can be done in several ways, such as using recursion (backtracking) or iteratively using bit manipulation. For an array of size `N`, there are `2^N - 1` non-empty combinations. The iterative bitmask approach is shown below. Each integer `i` from `1` to `2^N - 1` represents a unique subsequence, where the `j`-th bit of `i` being set means the `j`-th element of `candidates` is included in the subsequence.

```java
class Solution {
    public int largestCombination(int[] candidates) {
        int n = candidates.length;
        int maxSize = 0;

        // Iterate through all 2^n - 1 non-empty subsets
        for (int i = 1; i < (1 << n); i++) {
            int currentAnd = -1; // A value with all bits set
            int currentSize = 0;
            boolean firstElement = true;

            // Build the current combination based on the bits of i
            for (int j = 0; j < n; j++) {
                // Check if the j-th element is in the current subset
                if ((i & (1 << j)) != 0) {
                    if (firstElement) {
                        currentAnd = candidates[j];
                        firstElement = false;
                    } else {
                        currentAnd &= candidates[j];
                    }
                    currentSize++;
                }
            }

            if (currentAnd > 0) {
                maxSize = Math.max(maxSize, currentSize);
            }
        }
        return maxSize;
    }
}
```
This approach is too slow for the given constraints but is a valid starting point for understanding the problem.
### Algorithm
- 1. Initialize a variable `maxSize` to 0.
- 2. Generate all `2^N - 1` non-empty subsequences of the input array, where `N` is the number of candidates. This can be done by iterating from `1` to `2^N - 1` and using the bitmask of the iterator to select elements.
- 3. For each generated subsequence:
    - a. Initialize `currentAnd` with the first element of the subsequence.
    - b. Iterate through the rest of the elements of the subsequence and perform a bitwise AND operation with `currentAnd`.
    - c. After iterating through all elements, check if `currentAnd > 0`.
    - d. If it is, update `maxSize = max(maxSize, currentSubsequence.size())`.
- 4. After checking all subsequences, `maxSize` holds the result.

## Efficient Bit Counting
This approach leverages a key insight about the bitwise AND operation. For the AND of a set of numbers to be greater than zero, there must be at least one bit position that is '1' in every number of the set. The problem then transforms into finding the bit position that is set to '1' for the maximum number of candidates. This maximum count will be the size of the largest combination.
**Time:** O(N * K), where `N` is the number of candidates and `K` is the number of bits to check. Since `K` is a small constant (e.g., 24, based on the constraint `1 <= candidates[i] <= 10^7`), the complexity is effectively linear, `O(N)`. · **Space:** O(1). We only use a few variables to store counts, regardless of the input size. An alternative implementation might use an array of size 24 or 32 to store bit counts, which is still constant space.
**Pros:** Very efficient in both time and space.; Simple to implement once the core insight is understood.; Easily handles the given constraints.
**Cons:** Requires understanding the properties of the bitwise AND operation to arrive at the insight, making it less direct than the brute-force method.
### Explanation
Instead of checking combinations of numbers, we can check combinations of bits. For the bitwise AND of a group of numbers to be greater than 0, there must be at least one bit position `i` that is set to 1 for all numbers in that group. 

This means that any valid combination must consist entirely of numbers that share at least one common set bit. To find the largest such combination, we should find the bit position that is most frequently set across all numbers in the `candidates` array. 

The algorithm is as follows: we iterate through each possible bit position (from 0 up to a limit determined by the maximum possible value of a candidate). For each bit position, we count how many numbers in the `candidates` array have that bit set. The maximum count we find across all bit positions is our answer. Since the maximum candidate value is `10^7`, which is less than `2^24`, we only need to check bits 0 through 23.

```java
class Solution {
    public int largestCombination(int[] candidates) {
        int maxCount = 0;
        // The maximum value is 10^7, which is less than 2^24.
        // So we only need to check bits from 0 to 23.
        // We can iterate up to 30 for safety with standard integer sizes.
        for (int i = 0; i < 24; i++) {
            int currentCount = 0;
            for (int num : candidates) {
                // Check if the i-th bit is set in num
                // (num >> i) shifts the i-th bit to the least significant position
                // & 1 isolates this bit.
                if (((num >> i) & 1) == 1) {
                    currentCount++;
                }
            }
            maxCount = Math.max(maxCount, currentCount);
        }
        return maxCount;
    }
}
```
This approach is highly efficient and easily passes the given constraints.
### Algorithm
- 1. Initialize `maxCount = 0`.
- 2. Iterate through each bit position `i` from 0 to 23 (since `10^7 < 2^24`).
- 3. For each bit `i`:
    - a. Initialize `currentCount = 0`.
    - b. Iterate through each number `num` in the `candidates` array.
    - c. Check if the `i`-th bit is set in `num` using `(num >> i) & 1 == 1`.
    - d. If the bit is set, increment `currentCount`.
- 4. After iterating through all numbers for a given bit, update `maxCount = max(maxCount, currentCount)`.
- 5. After checking all bit positions, return `maxCount`.

# Solutions
### Java

```java
class Solution {
public
  int largestCombination(int[] candidates) {
    int ans = 0;
    for (int i = 0; i < 32; ++i) {
      int t = 0;
      for (int x : candidates) {
        t += (x >> i) & 1;
      }
      ans = Math.max(ans, t);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int largestCombination(vector<int> &candidates) {
    int mx = *max_element(candidates.begin(), candidates.end());
    int m = 32 - __builtin_clz(mx);
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      int cnt = 0;
      for (int x : candidates) {
        cnt += x >> i & 1;
      }
      ans = max(ans, cnt);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestCombination(self, candidates: List[int]) -> int: ans = 0 for i in range(32): t = 0 for x in candidates: t += (x >> i) & 1 ans = max(ans, t) return ans

```