Largest Combination With Bitwise AND Greater Than Zero

MEDIUM

Description

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 <= 10⁵
1 <= candidates[i] <= 10⁷

Approaches

Checkout 2 different approaches to solve Largest Combination With Bitwise AND Greater Than Zero. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

1. Initialize maxCount = 0.
1. Iterate through each bit position i from 0 to 23 (since 10^7 < 2^24).
1. 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.
1. After iterating through all numbers for a given bit, update maxCount = max(maxCount, currentCount).
1. After checking all bit positions, return maxCount.

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.

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.

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Largest Combination With Bitwise AND Greater Than Zero. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Largest Combination With Bitwise AND Greater Than Zero

Patterns:

Bit ManipulationCounting

Data Structures:

ArrayHash Table

Companies:

Jump Trading |