Skip to main content
Talentd

Prime Subset Selection I - Solution & Explanation

Medium11 min read
Practice this problem

Problem Statement

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 <= 106
  • 1 <= s <= 109

Approach Overview

Problem Overview: You are given an array of integers and need to select a subset of elements that satisfies a prime-based condition. The core work is deciding, quickly and repeatedly, whether a value is prime, so the choice of primality test drives the whole solution.

Approach 1: Brute Force with Trial Division (O(n * sqrt(M)) time, O(1) extra space)

For each element, test primality by trying every divisor from 2 up to the square root of the value. An element is kept or rejected based on the result. This is the simplest correct baseline and works fine for small inputs. Each check costs O(sqrt(M)), where M is the maximum value, so the total cost grows with both array length and value size. Prefer this only when values are small and the array is short.

Approach 2: Precomputed Sieve of Eratosthenes (O(M log log M) preprocessing, O(n) query time, O(M) space)

Build a boolean array marking all primes up to M in one pass. Start with every index marked prime, then cross out multiples of each prime starting at p squared. After preprocessing, each primality check is a single array lookup in O(1). You then scan the input once, looking up each element and applying the selection rule. Use this when the array is large or many values share the same range, since the sieve cost is paid once and amortized.

Approach 3: Frequency Counting Combined with the Sieve (O(n + M log log M) time, O(M) space)

When the condition depends on how often a prime value appears, store counts in a hash map or a fixed-size array indexed by value. Run the sieve, then make one pass over the frequency table instead of the raw array. This removes repeated work when duplicates are common. It is the most efficient option when values repeat heavily.

Recommended for interviews: The brute force shows you understand what primality means and how to test it. The sieve solution shows you recognize that the same check repeats across elements and that precomputation removes that cost. Explain the tradeoff between the two out loud, then implement the sieve. Practice related patterns in math, array, and hash table problems.

Solution

Thinking

The goal is to take as many primes as possible without letting their sum exceed s. With n up to 10^6 and s up to 10^9, a knapsack over subsets does not fit.

Among all subsets of a fixed size, the smallest sum comes from the smallest primes. The largest feasible size is therefore the longest prefix of the primes in increasing order whose sum is still at most s.

Sieve the primes up to 10^6 first. A query then takes them in order until the next prime is larger than n or larger than the remaining budget.

Use the sieve of Eratosthenes to precompute every prime up to 10^6 and store the primes in increasing order. For a query (n,s), scan that list from small to large. Stop when the current prime p is greater than n or greater than the remaining budget s; otherwise append p to the answer and subtract p from s.

The selected primes are the smallest ones that do not exceed n. They have the minimum sum among all subsets of the same size, so the size is already maximum. Any optimal subset is acceptable.

The sieve takes O(Mloglog M) time and O(M) space, where M=10^6. Each query takes O(\pi(n)) time, where \pi(n) is the number of primes not exceeding n.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force (Trial Division)O(n * sqrt(M))O(1)Small values and short arrays
Sieve of EratosthenesO(M log log M + n)O(M)General case, large arrays, many primality checks
Frequency Count + SieveO(M log log M + n)O(M)Many duplicate values

Video Solutions (6)

LeetCode | Weekly Contest 523 Q2 | Prime Subset Selection I | Sieve of Eratosthenes | C++

CodeSprint11:42108 views
Video 1 of 6

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Prime Subset Selection I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Prime Subset Selection II