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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public static int LargestCombination(List<int> candidates) {
6 int maxCount = 0;
7 for (int bit = 0; bit < 32; bit++) {
8 int count = 0;
9 foreach (int num in candidates) {
10 if ((num & (1 << bit)) != 0) {
11 count++;
12 }
13 }
14 maxCount = Math.Max(maxCount, count);
}
return maxCount;
}
public static void Main() {
List<int> candidates = new List<int> { 16, 17, 71, 62, 12, 24, 14 };
Console.WriteLine(LargestCombination(candidates));
}
}This C# method LargestCombination iterates over bit positions and counts the number of integers in the candidates list having each bit set, keeping track of the largest such count found.
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.