Largest subset with a non-zero bitwise AND

Given an array arr of positive integers, choose as many elements as you can so that the bitwise AND of all chosen elements is greater than 0. The chosen elements can come from anywhere in the array (they do not need to be adjacent), and each array position can be chosen at most once.

Return the number of elements in the largest such choice.

Implement:

def largest_and_subset(arr: list[int]) -> int: ...

Constraints

• 1 <= len(arr) <= 10^5
• 1 <= arr[i] <= 10^7

Example 1

Input:  arr = [5, 3, 6, 9]
Output: 3

5 (0101), 3 (0011) and 9 (1001) all have the lowest bit set, so 5 & 3 & 9 = 1 > 0. Adding 6 (0110) would clear that bit, and no bit is shared by all four.

Example 2

Input:  arr = [1, 2, 4, 8]
Output: 1

No two of these numbers share a set bit, so any single element is the best you can do.