Prime Subset Selection I Python solution

A Python solution builds a sieve with a bytearray or list of booleans up to the maximum value, marks composites by slicing multiples of each prime, then filters the input with one lookup per element. Use the sieve approach for the best time complexity. Python's slice assignment keeps the marking loop fast.

Is Prime Subset Selection I easy or hard?

It is rated Medium with a 42.3 percent acceptance rate. The difficulty comes from recognizing that repeated primality checks should be precomputed rather than recomputed. Once you know the sieve, the implementation is short and direct.

How to solve Prime Subset Selection I in O(n)?

Treat the sieve as a fixed cost and scan the input once. Build the prime table up to the maximum value, then iterate over the array and apply the selection rule with one lookup per element. The total work is linear in n once the sieve is built.

What is the best approach for Prime Subset Selection I?

The best approach is to precompute primality with a Sieve of Eratosthenes, then answer each check with a single array lookup. This gives O(M log log M) preprocessing and O(1) per check, where M is the maximum value. Use a frequency count if values repeat often.

What data structure is used in Prime Subset Selection I?

The main structure is a boolean array acting as the sieve, indexed by value. A hash map or frequency array is useful when you need counts of repeated values. Both give constant-time lookups, which keeps the per-element cost low.

What is the time complexity of Prime Subset Selection I?

The optimal solution runs in O(M log log M + n) time, where n is the array length and M is the largest value. The brute force trial division approach runs in O(n * sqrt(M)). Space for the optimal solution is O(M) for the sieve.

Is Prime Subset Selection I asked at Google, Amazon, or Meta?

The problem is tagged General on FleetCode, so no specific company tags are listed. Check the problem page on the source platform for current company tags. The sieve and primality techniques it uses come up often in interviews at large tech companies.

4079. Prime Subset Selection I - Practice Online

You are given two integers n and s.

Consider all prime numbers less than or equal to n. Select some of these primes such that:

The sum of the selected primes is less than or equal to s.
The number of selected primes is maximized.
Each prime can be selected at most once.

Return an integer array containing the selected primes in increasing order. If multiple optimal selections exist, return any of them.

If no prime can be selected, return an empty array.

Example 1:

Input: n = 7, s = 20

Output: [2,3,5,7]

Explanation:

The prime numbers less than or equal to n = 7 are 2, 3, 5, and 7.
The sum of all these primes is 2 + 3 + 5 + 7 = 17, which is less than or equal to s = 20.
Thus, the answer is [2, 3, 5, 7].

Example 2:

Input: n = 15, s = 15

Output: [3,5,7]

Explanation:

The prime numbers less than or equal to n = 15 are 2, 3, 5, 7, 11, and 13.
One possible selection is [3, 5, 7], whose sum is 3 + 5 + 7 = 15.
The four smallest available primes have sum 2 + 3 + 5 + 7 = 17, which exceeds s = 15. Therefore, selecting four or more primes is impossible, and the maximum number of selected primes is three.
Thus, [3, 5, 7] is one possible answer. Other valid answers include [2, 3, 5], [2, 3, 7], and [2, 5, 7].

Example 3:

Input: n = 5, s = 1

Output: []

Explanation:

The smallest prime number is 2, which is greater than s = 1.
Thus, no prime can be selected, so the answer is an empty array.

Constraints:

1 <= n <= 10⁶
1 <= s <= 10⁹