Sponsored
Sponsored
This approach focuses on determining how many numbers in the array have each particular bit set. The goal is to find the maximum count of numbers where at least one bit position has all of them contributing to a bitwise AND that results in a value greater than 0.
We iterate over each bit position (up to 32 if numbers can be up to 107) and count how many numbers have this bit set. The maximum of these counts is the size of the largest combination.
Time Complexity: O(n * 32) = O(n), where n is the number of candidates.
Space Complexity: O(1), no extra data structures are required beyond fixed-size variables.
1def largestCombination(candidates):
2 max_count = 0
3 for bit in range(32):
4 count = sum(1 for num in candidates if
The Python function largestCombination computes the bit count for each position using a generator expression inside the sum function, updating the maximal found count.
This approach leverages the fact that the bitwise AND of a combination of numbers will be non-zero only if there exists at least one bit position that is set in all numbers of the combination. We attempt to identify this by checking which bit has the maximum number of numbers with it set and then determining if these numbers can form a valid combination.
Time Complexity: O(n), iterating each bit for each number.
Space Complexity: O(1).
#include <iostream>
using namespace std;
int largestCombination(vector<int>& candidates) {
int maxCount = 0;
for (int bit = 0; bit < 32; bit++) {
int count = 0;
for (int num : candidates) {
if ((num & (1 << bit)) != 0) {
count++;
}
}
maxCount = max(maxCount, count);
}
return maxCount;
}
int main() {
vector<int> candidates = {16, 17, 71, 62, 12, 24, 14};
cout << largestCombination(candidates) << endl;
return 0;
}This C++ solution also checks each bit independently and counts numbers having the bit set, evaluating maximum possible combination size achieving AND > 0.