Largest subset with a non-zero bitwise AND

The AND of a group is non-zero exactly when at least one bit position is set
in every member of the group. So the question turns around: for each bit
b, the largest group whose AND keeps bit b is "all numbers that have bit
b set". Any group with a non-zero AND keeps some bit, so it fits inside one
of those per-bit groups. The answer is the largest per-bit count.

Brute force. Try every non-empty subset, AND its elements, and keep the
largest size with a non-zero result. That is O(2^n · n), fine for n ≤ 20
and a good way to say the problem out loud before you optimize.

Optimal. Count, for each bit position, how many numbers have it set. One
pass over the array per bit (or one pass with an inner loop over the bits).
Return the maximum count.

Why it is correct:

• Achievable: every number with bit b set shares bit b, so their AND
  has bit b and is > 0. A group of size count[b] always exists.
• Optimal: take any group with AND > 0. Pick a bit b set in that AND.
  Every member has bit b, so the group size is at most count[b].

Invariant: after processing the first i numbers, count[b] is how many of
them have bit b set. The width W is the bit length of the largest value
(about 24 bits for values up to 10^7, 31 for 32-bit signed ints).

Note what this does not say: the best group is not found by greedily
ANDing numbers together, and the answer is not tied to one particular value.
Two different bits can tie; either group is a valid answer.

from itertools import combinations
from typing import Iterable


def largest_and_subset(arr: list[int]) -> int:
    """Size of the largest subset whose bitwise AND is > 0.

    Assumes positive integers. Returns 0 for an empty array.
    """
    if not arr:
        return 0
    if any(x <= 0 for x in arr):
        raise ValueError("values must be positive integers")
    width = max(arr).bit_length()
    best = 0
    for b in range(width):
        mask = 1 << b
        count = sum(1 for x in arr if x & mask)
        best = max(best, count)
    return best


def largest_and_subset_members(arr: list[int]) -> list[int]:
    """One largest valid subset (returns the elements, not just the size)."""
    if not arr:
        return []
    width = max(arr).bit_length()
    counts = [0] * width
    for x in arr:
        for b in range(width):
            if x >> b & 1:
                counts[b] += 1
    best_bit = max(range(width), key=lambda b: counts[b])
    return [x for x in arr if x >> best_bit & 1]


class StreamingLargestAndSubset:
    """Follow-up: numbers arrive one by one, answer queries at any time."""

    def __init__(self, width: int = 32) -> None:
        self.counts = [0] * width

    def add(self, x: int) -> None:
        for b in range(len(self.counts)):
            if x >> b & 1:
                self.counts[b] += 1

    def remove(self, x: int) -> None:
        for b in range(len(self.counts)):
            if x >> b & 1:
                self.counts[b] -= 1

    def best(self) -> int:
        return max(self.counts, default=0)


def brute_force(arr: list[int]) -> int:
    """Reference answer for small inputs: try every subset."""
    best = 0
    for size in range(1, len(arr) + 1):
        for combo in combinations(arr, size):
            acc = combo[0]
            for x in combo[1:]:
                acc &= x
            if acc > 0:
                best = size
    return best


def _check(cases: Iterable[tuple[list[int], int]]) -> None:
    for arr, expected in cases:
        assert largest_and_subset(arr) == expected, (arr, expected)
        if arr:
            members = largest_and_subset_members(arr)
            acc = members[0]
            for x in members[1:]:
                acc &= x
            assert acc > 0 and len(members) == expected


if __name__ == "__main__":
    _check([
        ([5, 3, 6, 9], 3),
        ([7], 1),
        ([1, 2, 4, 8], 1),
        ([12, 10, 14, 6], 3),
        ([3, 3, 3], 3),
        ([], 0),
    ])
    import random
    for _ in range(300):
        arr = [random.randint(1, 64) for _ in range(random.randint(1, 9))]
        assert largest_and_subset(arr) == brute_force(arr), arr
    s = StreamingLargestAndSubset()
    for x in [12, 10, 14, 6]:
        s.add(x)
    assert s.best() == 3
    s.remove(14)
    assert s.best() == 2
    print("ok")

• largest_and_subset: O(n · W) time, where W is the bit length of the
  largest value (a constant ≤ 32 for 32-bit inputs, so effectively O(n)).
  O(1) extra space.
• largest_and_subset_members: O(n · W) time, O(W) space for the counts
  plus the output list.
• StreamingLargestAndSubset: add / remove are O(W); best is O(W)
  (or O(1) with a max-heap or a bucket of counts if queries dominate).
• Brute force: O(2^n · n) time.

• [5, 3, 6, 9] → 3 — bit 0 is set in 5, 3 and 9; 5 & 3 & 9 = 1.
• [7] → 1 — a single positive number is always valid.
• [1, 2, 4, 8] → 1 — powers of two share no bits.
• [12, 10, 14, 6] → 3 — bit 1 (value 2) is set in 10, 14, 6;
  10 & 14 & 6 = 2. Bit 2 (value 4) is set in 12, 14, 6 too: a tie.
• [3, 3, 3] → 3 — duplicates count separately.
• [] → 0 — no elements, nothing to choose.
• [2^30, 2^30 + 1, 1] → 2 — high bits matter; do not stop at 24 bits if
  the constraints allow larger values.
• n = 10^5 values all odd → 10^5 — linear time, no subset enumeration.

• Return the subset, not just its size. Remember which bit won, then
  filter the array by that bit (largest_and_subset_members). Same
  O(n · W).
• Streaming / sliding window. Keep the per-bit counts and update them on
  each add or remove in O(W). For "largest valid subset inside the last
  k numbers", add the new number and remove the one leaving the window.
• Many range queries [l, r]. Build a prefix count per bit
  (W arrays of length n + 1). Each query is max_b(pref[b][r+1] - pref[b][l]),
  O(W) per query after O(n · W) setup.
• AND must be ≥ a threshold T, or must contain a given mask M. For a
  required mask, keep only numbers with x & M == M and count them. For
  "AND ≥ T" the per-bit trick no longer works directly; walk bits from high
  to low like a trie/greedy over prefixes: try to fix each high bit to 1
  while the candidate set stays large enough, which is a different problem.
• OR / XOR variants. "Largest subset with OR equal to X" or
  "XOR > 0" break the per-bit independence; discuss why AND is special (it
  only removes bits, so a group's AND is non-zero iff one bit survives in
  all members).

Mid-level (L4)

• States the brute force and its cost, then finds the "some bit survives in
  every member" observation with light hints.
• Writes the per-bit counting loop correctly, including bit width and empty
  input.
• Walks through one example by hand.

Senior (L5)

• Gets to the per-bit insight unprompted and proves both directions
  (achievable and optimal).
• Gives O(n · W) time, O(1) space, and explains why W comes from the
  value range, not n.
• Handles follow-ups: return the members, streaming counts, prefix sums for
  range queries.

Staff (L6+)

• Generalizes: AND is monotone (only clears bits), which is what makes the
  decomposition work; explains why OR/XOR/threshold variants need other
  tools.
• Discusses input contracts (zeros, negatives, 64-bit values) and testing
  against a brute-force oracle with randomized inputs.
• Talks about vectorization or parallel per-bit counting for very large
  inputs, and keeps the code simple and readable.