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 num & (1 << bit))
5 max_count = max(max_count, count)
6 return max_count
7
8candidates = [16, 17, 71, 62, 12, 24, 14]
9print(largestCombination(candidates))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).
This C solution checks for the highest count of numbers with a particular bit set, using steps similar to Approach 1, while considering each bit in isolation to determine maximum combination size potential.