Largest Combination With Bitwise AND Greater Than Zero - Video Solutions

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.