2275. Largest Combination With Bitwise AND Greater Than Zero

The problem

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Compute the bitwise AND for all possible combinations of elements in the candidates array.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

Example 1:

Input: candidates = [16,17,71,62,12,24,14]
Output: 4
Explanation: The combination [16,17,62,24] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination [62,12,24,14] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

Example 2:

Input: candidates = [8,8]
Output: 2
Explanation: The largest combination [8,8] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.

Constraints:

1 <= candidates.length <= 10⁵
1 <= candidates[i] <= 10⁷

Approach overview

Problem Overview: You are given an array of positive integers. The task is to choose the largest possible subset such that the bitwise AND of all chosen numbers is greater than zero. For the AND result to stay positive, every number in the subset must share at least one common bit set to 1.

Approach 1: Bit Counting (O(32 * n) time, O(1) space)

The key observation is that a positive AND result means at least one bit position remains set after combining all numbers. Instead of testing every subset, count how many numbers have each bit set. Iterate through every number and check each of the 32 bit positions using a bit mask like (num >> bit) & 1. Maintain a counter for each bit. The largest counter represents the maximum number of values that share that bit, meaning their AND will keep that bit as 1. The answer is simply the maximum frequency among all bit positions. This approach works because a subset with the same set bit guarantees the AND result remains non‑zero. The algorithm scans the array once and checks 32 bits per number, giving O(32 * n) time and constant memory.

This technique is a classic pattern when working with bit manipulation problems: instead of evaluating combinations directly, analyze bit positions independently and aggregate counts. It avoids exponential subset checks and converts the task into a simple counting pass.

Approach 2: Bit Manipulation with Early Exit (O(32 * n) time, O(1) space)

This variation follows the same bit counting idea but adds an optimization during iteration. For each bit position, scan the array and count how many numbers contain that bit. While scanning, track the remaining elements. If the current count plus the remaining possible elements cannot exceed the best answer found so far, you can stop processing that bit early. This pruning reduces unnecessary checks in cases where an early candidate already has a large frequency. The logic still relies on the same core observation: the maximum subset corresponds to the most frequent set bit.

Even with early termination, the theoretical complexity remains O(32 * n), but in practice it can skip work on dense inputs. The approach relies purely on integer bit checks and counters, making it memory efficient and easy to implement in languages like Python, Java, or C++.

Recommended for interviews: Interviewers expect the bit counting solution. A brute force subset check would be exponential and impractical. Recognizing that the AND result depends on shared bit positions demonstrates strong understanding of bit manipulation and counting techniques. Implementing the simple 32-bit frequency scan is both optimal and clean.

Approach 1: Approach 1: Bit Counting

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 10⁷) and count how many numbers have this bit set. The maximum of these counts is the size of the largest combination.

Python

def largestCombination(candidates):
    max_count = 0
    for bit in range(32):
        count = sum(1 for num in candidates if num & (1 << bit))
        max_count = max(max_count, count)
    return max_count

candidates = [16, 17, 71, 62, 12, 24, 14]
print(largestCombination(candidates))

Java

import java.util.List;

public class Solution {
    public static int largestCombination(List<Integer> 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 = Math.max(maxCount, count);
        }
        return maxCount;
    }

    public static void main(String[] args) {
        List<Integer> candidates = List.of(16, 17, 71, 62, 12, 24, 14);
        System.out.println(largestCombination(candidates));
    }
}

C++

#include <vector>
#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)) {
                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;
}

JavaScript

function largestCombination(candidates) {
    let maxCount = 0;
    for (let bit = 0; bit < 32; bit++) {
        let count = 0;
        for (const num of candidates) {
            if (num & (1 << bit)) {
                count++;
            }
        }
        maxCount = Math.max(maxCount, count);
    }
    return maxCount;
}

const candidates = [16, 17, 71, 62, 12, 24, 14];
console.log(largestCombination(candidates));

#include <stdio.h>

int largestCombination(int* candidates, int candidatesSize) {
    int maxCount = 0;
    for (int bit = 0; bit < 32; bit++) {
        int count = 0;
        for (int i = 0; i < candidatesSize; i++) {
            if (candidates[i] & (1 << bit)) {
                count++;
            }
        }
        if (count > maxCount) {
            maxCount = count;
        }
    }
    return maxCount;
}

int main() {
    int candidates[] = {16, 17, 71, 62, 12, 24, 14};
    int size = sizeof(candidates)/sizeof(candidates[0]);
    printf("%d\n", largestCombination(candidates, size));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static int LargestCombination(List<int> candidates) {
        int maxCount = 0;
        for (int bit = 0; bit < 32; bit++) {
            int count = 0;
            foreach (int num in candidates) {
                if ((num & (1 << bit)) != 0) {
                    count++;
                }
            }
            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));
    }
}

The Python function largestCombination computes the bit count for each position using a generator expression inside the sum function, updating the maximal found count.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Approach 2: Bit Manipulation with Early Exit

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.

Python

def largestCombination(candidates):
    max_count = 0
    for bit in range(32):
        count = sum(1 for num in candidates if num & (1 << bit))
        max_count = max(max_count, count)
    return max_count

candidates = [16, 17, 71, 62, 12, 24, 14]
print(largestCombination(candidates))

Java

import java.util.List;

public class Solution {
    public static int largestCombination(List<Integer> candidates) {
        int maxCount = 0;
        for (int bit = 0; bit < 32; bit++) {
            int count = 0;
            int requiredValue = (1 << bit);
            for (int num : candidates) {
                if ((num & requiredValue) != 0) {
                    count++;
                }
            }
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }

    public static void main(String[] args) {
        List<Integer> candidates = List.of(16, 17, 71, 62, 12, 24, 14);
        System.out.println(largestCombination(candidates));
    }
}

C++

#include <vector>
#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;
}

JavaScript

function largestCombination(candidates) {
    let maxCount = 0;
    for (let bit = 0; bit < 32; bit++) {
        let count = 0;
        const requiredValue = (1 << bit);
        for (const num of candidates) {
            if (num & requiredValue) {
                count++;
            }
        }
        maxCount = Math.max(maxCount, count);
    }
    return maxCount;
}

const candidates = [16, 17, 71, 62, 12, 24, 14];
console.log(largestCombination(candidates));

#include <stdio.h>

int largestCombination(int* candidates, int candidatesSize) {
    int maxCount = 0;
    for (int bit = 0; bit < 32; bit++) {
        int count = 0;
        int requiredValue = (1 << bit);
        for (int i = 0; i < candidatesSize; i++) {
            if (candidates[i] & requiredValue) {
                count++;
            }
        }
        if (count > maxCount) {
            maxCount = count;
        }
    }
    return maxCount;
}

int main() {
    int candidates[] = {16, 17, 71, 62, 12, 24, 14};
    int size = sizeof(candidates)/sizeof(candidates[0]);
    printf("%d\n", largestCombination(candidates, size));
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static int LargestCombination(List<int> candidates) {
        int maxCount = 0;
        for (int bit = 0; bit < 32; bit++) {
            int count = 0;
            int requiredValue = (1 << bit);
            foreach (int num in candidates) {
                if ((num & requiredValue) != 0) {
                    count++;
                }
            }
            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));
    }
}

The Python function maintains simplicity by checking each bit separately, ensuring the group size is maximized by meeting non-zero AND criteria.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Bit Manipulation

The problem requires finding the maximum length of a combination of numbers where the bitwise AND result is greater than 0. This implies that there must be a certain binary bit where all numbers have a 1 at that position. Therefore, we can enumerate each binary bit and count the number of 1s at that bit position for all numbers. Finally, we take the maximum count.

The time complexity is O(n times log M), where n and M are the length of the array candidates and the maximum value in the array, respectively. The space complexity is O(1).

TypeScript

function largestCombination(candidates: number[]): number {
    const mx = Math.max(...candidates);
    const m = mx.toString(2).length;
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        let cnt = 0;
        for (const x of candidates) {
            cnt += (x >> i) & 1;
        }
        ans = Math.max(ans, cnt);
    }
    return ans;
}

func largestCombination(candidates []int) (ans int) {
	mx := slices.Max(candidates)
	m := bits.Len(uint(mx))
	for i := 0; i < m; i++ {
		cnt := 0
		for _, x := range candidates {
			cnt += (x >> i) & 1
		}
		ans = max(ans, cnt)
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Bit Counting	Time Complexity: O(n). Space Complexity: O(1).
Approach 2: Bit Manipulation with Early Exit	Time Complexity: O(n). Space Complexity: O(1).
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Bit Counting	O(32 * n)	O(1)	Best general solution. Simple implementation that counts how many numbers share each bit.
Bit Manipulation with Early Exit	O(32 * n)	O(1)	Useful when large counts appear early, allowing early termination during scans.

Frequently asked questions

Is Largest Combination With Bitwise AND Greater Than Zero easy or hard?

The problem is rated Medium on LeetCode. The implementation is straightforward once you realize that the AND result depends on shared bit positions, but identifying the bit-counting insight is the key step.

Largest Combination With Bitwise AND Greater Than Zero Python/Java solution

In Python or Java, iterate through numbers and check each bit using shift operations. Maintain a 32-length array that counts occurrences of each bit. The answer is the maximum value in this array. The same logic translates directly to C++, C#, and JavaScript.

How to solve Largest Combination With Bitwise AND Greater Than Zero in O(n)?

Treat each bit position independently. For every bit from 0 to 31, count how many numbers contain that bit using a shift operation like (num >> bit) & 1. The largest count among these positions represents the largest subset whose bitwise AND keeps that bit set. This yields an O(n) practical runtime since the number of bits is fixed.

What is the best approach for Largest Combination With Bitwise AND Greater Than Zero?

The optimal approach is bit counting. Iterate through each of the 32 bit positions and count how many numbers in the array have that bit set. The maximum count represents the largest subset where the bitwise AND remains greater than zero. This runs in O(32 * n) time with O(1) extra space.

Is Largest Combination With Bitwise AND Greater Than Zero asked at Google/Amazon/Meta?

Bit manipulation and counting problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. The problem tests whether you can recognize patterns in bitwise operations and reduce subset problems into frequency counting.

What data structure is used in Largest Combination With Bitwise AND Greater Than Zero?

The solution mainly relies on simple counters or a fixed-size array of length 32 to track bit frequencies. No complex data structures are required; the problem focuses on bit manipulation and counting techniques.

What is the time complexity of Largest Combination With Bitwise AND Greater Than Zero?

The optimal solution runs in O(32 * n) time because each number is checked against 32 possible bit positions. Since 32 is constant for standard integers, the complexity is effectively O(n). Space complexity is O(1) because only a few counters are stored.

Largest Combination With Bitwise AND Greater Than Zero solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Bit Counting

Approach 2: Approach 2: Bit Manipulation with Early Exit

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Largest Combination With Bitwise AND Greater Than Zero solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Bit Counting

Approach 2: Approach 2: Bit Manipulation with Early Exit

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems