Largest Combination With Bitwise AND Greater Than Zero

Medium
1325.

Largest Combination With Bitwise AND Greater Than Zero

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.

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^5
  • 1 <= candidates[i] <= 10^7
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} candidates
 * @return {number}
 */
var largestCombination = function(candidates) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= candidates[i] <= 10^7

Hints for Largest Combination With Bitwise AND Greater Than Zero

  1. Hint 1

    When is an AND greater than zero? Some bit must survive in every selected element.

  2. Hint 2

    Fix a bit position. Which elements can join a combination that keeps that bit?

  3. 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

  1. For each bit position b from 0 to 23 (10^7 < 2^24), count how many candidates have bit b set.
  2. 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 best

Java

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