Largest Combination With Bitwise AND Greater Than Zero Solution
Largest Combination With Bitwise AND Greater Than Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Largest Combination With Bitwise AND Greater Than Zero is a medium coding problem on arrays, hash table and bit manipulation, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Bit Manipulation, Counting
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of positive integers candidates. A combination is any non-empty selection of elements of candidates, each element used at most once; its bitwise AND is the AND of every selected element.
Return the size of the largest combination whose bitwise AND is greater than 0.
Example 1
Input: candidates = [5,3,6]
Output: 2
Explanation: Any two of them share a bit (`5 AND 3 = 1`), but `5 AND 3 AND 6 = 0`.
Example 2
Input: candidates = [8,8]
Output: 2
Example 3
Input: candidates = [1,2,4]
Output: 1
Explanation: No two values share a bit, so only single elements qualify.
Constraints
1 <= candidates.length <= 10^51 <= candidates[i] <= 10^7
Hints for Largest Combination With Bitwise AND Greater Than Zero
Hint 1
When is an AND greater than zero? Some bit must survive in every selected element.
Hint 2
Fix a bit position. Which elements can join a combination that keeps that bit?
Hint 3
For every bit, count the candidates that have it set; the answer is the largest count.
How to solve Largest Combination With Bitwise AND Greater Than Zero
An AND is positive exactly when at least one bit is set in every chosen element, so the best combination is "all candidates that have bit b" for the best bit b.
Approach
- For each bit position b from 0 to 23 (10^7 < 2^24), count how many candidates have bit b set.
- Return the largest of those counts.
Why it works
If a combination's AND is positive, some bit b survives, so every member has bit b and the combination is no larger than the count for b. Conversely, taking every candidate with bit b gives an AND that still has bit b, so that count is achievable. The answer is therefore the maximum count over bits.
Complexity
- Time —
O(24 · n) - Space —
O(1)
Pitfalls
- Enumerating combinations is exponential — the per-bit view removes the search entirely.
- The surviving bits of the best combination need not be the highest bit of any element.
- Every candidate is positive, so the answer is always at least 1.
Reference solution
Python
from typing import List
def largestCombination(candidates: List[int]) -> int:
best = 0
for b in range(24):
cnt = 0
for v in candidates:
cnt += (v >> b) & 1
if cnt > best:
best = cnt
return bestJava
public static int largestCombination(int[] candidates) {
int best = 0;
for (int b = 0; b < 24; b++) {
int cnt = 0;
for (int v : candidates) cnt += (v >> b) & 1;
best = Math.max(best, cnt);
}
return best;
}C++
int largestCombination(vector<int>& candidates) {
int best = 0;
for (int b = 0; b < 24; b++) {
int cnt = 0;
for (int v : candidates) cnt += (v >> b) & 1;
best = max(best, cnt);
}
return best;
}JavaScript
var largestCombination = function(candidates) {
var best = 0;
for (var b = 0; b < 24; b++) {
var cnt = 0;
for (var i = 0; i < candidates.length; i++) cnt += (candidates[i] >> b) & 1;
if (cnt > best) best = cnt;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets