Skip to main content
Talentd

Largest Combination With Bitwise AND Greater Than Zero - Solution & Explanation

MediumArrayHash TableBit ManipulationCounting16 min readAsked at: Amazon, Adobe, Google +1
Practice this problem

Problem Statement

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 <= 105
  • 1 <= candidates[i] <= 107

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

This C program defines a function largestCombination that takes an array of candidates and its size, then iterates over all 32 possible bit positions. For each bit position, it counts how many numbers in the array have that bit set, maintaining a maximum count found so far.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), iterating each bit for each number.
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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Bit Counting

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.

Approach 2: Bit Manipulation with Early Exit

Time Complexity: O(n), iterating each bit for each number.
Space Complexity: O(1).

Bit Manipulation—

Detailed Complexity Analysis

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

Video Solution

Largest Combination With Bitwise AND Greater Than Zero | Detailed | Leetcode 2275 | codestorywithMIK • codestorywithMIK • 9,172 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Largest Combination With Bitwise AND Greater Than Zero with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Number of Maximum Bitwise-OR Subsets