Maximum Number That Makes Result of Bitwise AND Zero - Solution & Explanation

Problem Overview: You are given an array of integers and need the maximum number of elements you can select such that their combined bitwise AND does not collapse to zero. The key observation is that the AND operation preserves a bit only if every selected number contains that bit.

Approach 1: Brute Force Subset Check (Exponential Time)

Generate all possible subsets and compute the bitwise AND for each subset. Track the largest subset whose result is non-zero. This approach directly models the definition but becomes infeasible quickly because the number of subsets grows as 2^n. Time complexity is O(2^n * n) since each subset may require recomputing the AND across its elements. Space complexity is O(1) excluding recursion or subset storage. Useful only for understanding the behavior of the AND operation on small inputs.

Approach 2: Bit Frequency Counting (Bit Manipulation Greedy) (O(n log A))

The AND of multiple numbers remains non-zero only if there exists at least one bit position where every chosen number has a 1. Instead of checking subsets, iterate through each bit position and count how many numbers contain that bit. If k numbers share the same set bit, their AND will keep that bit, guaranteeing a non-zero result. The maximum valid subset size therefore equals the largest count among all bit positions. Iterate through numbers, check bits using (num >> bit) & 1, and track frequencies. Time complexity is O(n log A) where A is the maximum value (number of bits). Space complexity is O(log A) for bit counters.

This approach relies heavily on bit manipulation and a simple greedy observation: maximizing the group sharing a common bit maximizes the subset that keeps the AND result non-zero. Sorting is unnecessary for the optimal approach, though understanding binary representation patterns is helpful.

Recommended for interviews: The bit counting strategy is what interviewers expect. It reduces an exponential subset search into a linear scan across numbers and bit positions. Mentioning the brute force idea shows understanding of the AND property, but recognizing that a shared bit guarantees a non-zero result demonstrates strong problem decomposition and familiarity with bit-level reasoning.