Largest Subset With Positive Bitwise AND

Problem Statement

Given an array of positive integers nums, find the size of the largest subset such that the bitwise AND of all elements in the subset is greater than 0.

Two integers a and b have a bitwise AND greater than 0 if there exists at least one bit position k (where 0 <= k < 31) such that both a and b have a 1 at that position. Since we want the AND of the entire subset to be positive, all elements in your chosen subset must share at least one common bit set to 1 at the same position k.

Function Signature

def largest_subset_bitwise_and(nums: list[int]) -> int:

Examples

Example 1: Input: nums = [1, 2, 3, 4] Output: 2 Explanation: The binary representations are 001, 010, 011, 100. If we pick the bit at position 0, elements 1 and 3 share it (AND = 1). If we pick position 1, elements 2 and 3 share it (AND = 2). Max size is 2.

Example 2: Input: nums = [16, 17, 18, 19] Output: 4 Explanation: All numbers share the bit at position 4 (value 16). The AND of the entire set is 16, which is > 0.

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

Edge Cases

• Array with a single element.
• Array where no two numbers share a bit (the answer should be 1).