Approach
To solve this problem, we first assume that all the elements are included in our answer and calculate the sum of all the elements in our input.
We later check if the sum is prime. If not, we can print the whole input as our answer. If the sum happens to be prime, we can remove one odd element from the set of all elements.
An array with a prime sum must have an odd element (the only exception is when the sum is 2), and removing an odd element from the sum will make the sum composite (except when the sum becomes 2, i.e. when there’s an odd element and a ‘2’ in the array and their combined sum is prime). This results in two special cases that need to be handled separately.
The code follows the following steps to implement the above idea.
-
Make a function isPrime to check if a number is prime. Refer to the following link here to understand this primality test and many more.
- Our first step is to find the sum of all elements in the input. We check if the sum <= 2. If this is the case, we print a -1 (no valid answer exists).
- We then use the isPrime function to check if the sum is prime or not. If not then we can just print the whole input as our solution.
- If the sum is a prime number, we identify an odd element to remove (here, if there's only one element, we print -1). Here we need to pay attention to the special case where the size of the array is 2 and it consists of an odd number and '2' in the array.
- In this special case, if the odd number is composite, we can print that as the answer or print -1 as there isn't a valid answer for the input.
- In the end, we need to print the solution (the subset size and one of the valid subsets along with it), excluding one odd number that we determined earlier.
Code in C++
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
bool isPrime(int x){
// there are better alternatives
// and improvements possible
// like rabin miller test or skipping check over even elements, etc
for(int i = 2; i * i <= x; i++){
if(x % i == 0) return false;
}
return true;
}
void LargestSubsetWithCompositeSum(vector<int> a, int n){
// sum of the elements in the vector
int sum_of_elements = 0;
for(int i = 0; i < n; i++){
sum_of_elements += a[i];
}
//edge case when sum <= 2
if(sum_of_elements <= 2){
cout << -1 << endl;
return;
}
if(isPrime(sum_of_elements)){
// remove one odd element and print
// print all elements except one odd element
if(n == 1){
cout << -1 << endl;
return;
}
bool odd_found = -1;
for(int i = 0; i < n; i++){
if(a[i] % 2 == 1){
odd_found = i;
break;
}
}
// if the sum is a prime number then it must have an odd number
assert(odd_found != -1);
if(n == 2 && a[1 - odd_found] == 2){
// special case when there's one odd and 2 in the array
// if the odd number is not prime then we print it
if(!isPrime(a[odd_found])){
cout << 1 << endl;
cout << a[odd_found] << endl;
}
else{
cout << -1 << endl;
}
return;
}
cout << n - 1 << endl;
// print all elements except the one at index odd_found
for(int i = 0; i < odd_found; i++){
cout << a[i] << " ";
}
for(int i = odd_found + 1; i < n; i++){
cout << a[i] << " ";
}
cout << endl;
}
else{
//print all elements
cout << n << endl;
for(int i = 0; i < n; i++){
cout << a[i] << " ";
}
cout << endl;
}
}
int32_t main(){
// change input here
vector<int> a = {15, 2};
int n = a.size();
LargestSubsetWithCompositeSum(a, n);
}
You can also try this code with Online C++ Compiler
Output
6
3 1 8 4 9 5
Complexity Analysis
Time Complexity
The time complexity of the above code is O(N + sqrt(sum_of_elements)). O(N) time is taken to compute the sum and print the answer, while O(sqrt(sum_of_elements)) time is taken to determine if the sum of the elements is prime.
Space Complexity
The space complexity of the solution is O(1), as the space required by the algorithm to run doesn't depend on the input's size.
Frequently Asked Questions
Why does checking for a valid factor up to sqrt(n) work?
Let's assume that some factor is larger than sqrt(n). Let's call it P. Then we can claim that P * Q = n, for some Q. Here Q is bound to be less than sqrt(n), and we have found a valid factor below sqrt(n). Therefore it's sufficient to traverse for factors up to sqrt(n).
Where can I learn more about number theory basics?
You can find multiple articles and problems related to number theory on code studio. Here is a resource to get you started. It's best to start with the resources here and practice problems to help increase your familiarity with the topic.
What are other methods to check if a number is prime?
There are many tests to check if a number is prime, Fermat's test, and Rabin Miller's test are some of the famous ones, but they are non-deterministic, i.e., they can't say with 100% if the number is prime. However, you can find deterministic versions of the Rabin Miller test for all numbers under 264. They offer an improvement over the test we used earlier and can be used when sums of all elements reach as large as 1018.
Conclusion
The article helps us use number theory basics to solve a problem and identify special cases. To understand the article well, learn more about primality tests here and Number Theory here.
Learn more about the C++ STL library from here if you have trouble understanding some parts of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas. You can check out our Top Array Coding Interview Questions for more practice.
Recommended Articles
Subset Sum problem
Sum of beauty in the array
Jump Game
Recommended Problems:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy learning!
39+ registered 
