Quick Overview

Find the largest subset of integers whose bitwise AND is positive under the stated constraints. Cover edge cases and complexity, then consider follow-ups that return indices or require several surviving bits.

Largest Subset With Positive Bitwise AND

Company: Jump Trading

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

## Problem Implement `largest_positive_and_subset(nums)`. Choose a nonempty subset of the given nonnegative integers. The subset is valid when the bitwise AND of all selected values is strictly positive. Return the largest possible subset size. If no valid subset exists, return `0`. ## Constraints - `1 <= len(nums) <= 200,000` - `0 <= nums[i] < 2^31` - Elements are selected by index, so duplicate values count as separate choices. - The selected elements do not need to be contiguous. ## Clarifications The bitwise AND must be greater than zero, not merely nonnegative. You only need the maximum size, not the subset itself. ## Examples `[5, 3, 10, 7]` returns `3`. For example, `5`, `3`, and `7` all have their least-significant bit set, so their AND is positive. `[0, 0, 0]` returns `0`. `[6, 14, 2, 7]` returns `4` because all four values have the bit with value `2` set, so their combined AND is positive. ## Hint If an AND result is positive, at least one bit survives in every selected value. Turn that observation into a counting problem over bit positions. ## Interview Follow-ups - Return one maximum subset of indices. - Generalize the requirement so the AND must contain at least two set bits. - Explain why enumerating subsets is unnecessary.

Quick Answer: Find the largest subset of integers whose bitwise AND is positive under the stated constraints. Cover edge cases and complexity, then consider follow-ups that return indices or require several surviving bits.

Implement `largest_positive_and_subset(nums)`. Choose a nonempty subset of the given nonnegative integers. A subset is valid when the bitwise AND of all selected values is strictly positive. Return the largest possible subset size, or `0` when no valid subset exists. Elements are selected by index, so duplicate values count as separate choices, and the selected elements need not be contiguous.

Constraints

  • 1 <= len(nums) <= 200,000
  • 0 <= nums[i] < 2^31
  • Elements are selected by index, so duplicate values count as separate choices.
  • The selected elements do not need to be contiguous.

Examples

Input: ([0],)

Expected Output: 0

Explanation: The only nonempty subset has AND zero, so no valid subset exists.

Input: ([2],)

Expected Output: 1

Explanation: The positive singleton has bit 1 set and is itself a valid subset.

Hints

  1. If an AND result is positive, at least one bit survives in every selected value. Turn that observation into a counting problem over bit positions.

Loading coding console...