Given an array A[], find a subset of maximum size in which sum of every pair of elements is a prime number. Print its length and the subset. Consider many queries for different arrays and maximum value of an element as 100000.
Examples :
Input : A[] = {2, 1, 2}
Output : 2
1 2
Explanation :
Here, we can only form subsets with size 1 and 2.
maximum sized subset = {1, 2}, 1 + 2 = 3, which
is prime number.
So, Answer = 2 (size), {1, 2} (subset)
Input : A[] = {2, 1, 1}
Output : 3
1 1 2
Explanation :
Maximum subset = {2, 1, 2}, since 1 + 2 = 3,
1 + 1 = 2, both are prime numbers.
Answer = 3 (size), {2, 1, 1} (subset).
Let’s make some observations and then move to problem. Sum of two numbers is even if and only both the numbers are either odd or even. An even number cannot be a prime number except 2. Now, if we take three numbers a, b and c, two of them should be either odd or even(Pigeonhole theorem). So, our solution exists only in two cases – (Let the subset be B)
- Case I : When B contains only two integers(>1) whose sum is a prime number.
- Case II : When B contains some number of ones(1s) and another number X, where X + 1 should be a prime(Only possible when X is an even number).
First count the number of ones in the array using a for loop.
- If the count of 1s is greater than 0, then traverse the whole the array and check if [A[i] + 1] is a prime number and (A[i] != 1), if found any, print the size of subarray as (count of 1s) +1 and all the ones(1s) and the found A[i]. Exit the program.
- If the above step fails (i.e, A[i] not found), print all the ones(1s). Exit the program.
- If above step fails (i.e, count of 1s = 0), Check every pair of elements in the array for their sum to be a prime. Print 2 and the pair of integers.
- Else Print -1.
Below is implementation of above approach :
C++
// CPP program to find a subset in which sum of // every pair in it is a prime#include <bits/stdc++.h>using namespace std;#define MAX 100001bool isPrime[MAX] = { 0 };int sieve(){ for (int p = 2; p * p < MAX; p++) { // If isPrime[p] is not changed, then it // is a prime if (isPrime[p] == 0) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) isPrime[i] = 1; } }}int findSubset(int a[], int n){ int cnt1 = 0; // Counting no.of ones in the array for (int i = 0; i < n; i++) if (a[i] == 1) cnt1++; // Case-I: count of ones(1s) > 0 and // an integer > 1 is present in the array if (cnt1 > 0) { for (int i = 0; i < n; i++) { // Find a[i], where a[i] + 1 is prime. if ((a[i] != 1) and (isPrime[a[i] + 1] == 0)) { cout << cnt1 + 1 << endl; // Print all the ones(1s). for (int j = 0; j < cnt1; j++) cout << 1 << " "; cout << a[i] << endl; // print a[i]. return 0; } } } // Case-II: array contains only ones(1s) if (cnt1 >= 2) { cout << cnt1 << endl; // Print all ones(1s). for (int i = 0; i < cnt1; i++) cout << 1 << " "; cout << endl; return 0; } // Case-III: array does not contain 1s for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Find a pair of integers whose sum is prime if (isPrime[a[i] + a[j]] == 0) { cout << 2 << endl; cout << a[i] << " " << a[j] << endl; return 0; } } } // Array contains only a single element. cout << -1 << endl;}// Driver functionint main(){ sieve(); int A[] = { 2, 1, 1 }; int n = sizeof(A) / sizeof(A[0]); findSubset(A, n); return 0;} |
Java
// Java program to find a // subset in which sum of // every pair in it is a primeimport java.io.*;class GFG{ static int MAX = 100001; static int []isPrime = new int[MAX]; static int sieve() { for (int p = 2; p * p < MAX; p++) { // If isPrime[p] is // not changed, then // it is a prime if (isPrime[p] == 0) { // Update all // multiples of p for (int i = p * 2; i < MAX; i += p) isPrime[i] = 1; } } return -1; } static int findSubset(int []a, int n) { int cnt1 = 0; // Counting no. of // ones in the array for (int i = 0; i < n; i++) if (a[i] == 1) cnt1++; // Case-I: count of // ones(1s) > 0 and // an integer > 1 is // present in the array if (cnt1 > 0) { for (int i = 0; i < n; i++) { // Find a[i], where // a[i] + 1 is prime. if ((a[i] != 1) && (isPrime[a[i] + 1] == 0)) { System.out.println(cnt1 + 1); // Print all // the ones(1s). for (int j = 0; j < cnt1; j++) System.out.print(1 + " "); System.out.println(a[i]); // print a[i]. return 0; } } } // Case-II: array contains // only ones(1s) if (cnt1 >= 2) { System.out.println(cnt1); // Print all ones(1s). for (int i = 0; i < cnt1; i++) System.out.print(1 + " "); System.out.println(); return 0; } // Case-III: array does // not contain 1s for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Find a pair of integers // whose sum is prime if (isPrime[a[i] + a[j]] == 0) { System.out.println(2); System.out.println(a[i] + " " + a[j]); return 0; } } } // Array contains only // a single element. System.out.println(-1); return -1; } // Driver Code public static void main(String args[]) { sieve(); int []A = new int[]{ 2, 1, 1 }; int n = A.length; findSubset(A, n); }}// This code is contributed by // Manish Shaw(manishshaw1) |
Python3
# Python3 program to find a subset in which # sum of every pair in it is a primeimport math as mtMAX = 100001isPrime = [0 for i in range(MAX)]def sieve(): for p in range(2, mt.ceil(mt.sqrt(MAX))): # If isPrime[p] is not changed, # then it is a prime if (isPrime[p] == 0) : # Update all multiples of p for i in range(2 * p, MAX, p): isPrime[i] = 1def findSubset(a, n): cnt1 = 0 # Counting no.of ones in the array for i in range(n): if (a[i] == 1): cnt1+=1 # Case-I: count of ones(1s) > 0 and # an integer > 1 is present in the array if (cnt1 > 0): for i in range(n): # Find a[i], where a[i] + 1 is prime. if ((a[i] != 1) and (isPrime[a[i] + 1] == 0)): print(cnt1 + 1) # Print all the ones(1s). for j in range(cnt1): print("1", end = " ") print(a[i]) return 0 # Case-II: array contains only ones(1s) if (cnt1 >= 2): print(cnt1) # Print all ones(1s). for i in range(cnt1): print("1", end = " ") print("\n") return 0 # Case-III: array does not contain 1s for i in range(n): for j in range(i + 1, n): # Find a pair of integers whose # sum is prime if (isPrime[a[i] + a[j]] == 0): print(2) print(a[i], " ", a[j]) # Array contains only a single element. print(-1)# Driver Codesieve()A =[ 2, 1, 1]n =len(A)findSubset(A, n)# This code is contributed # by Mohit kumar 29 |
C#
// C# program to find a subset // in which sum of every pair // in it is a primeusing System;class GFG{ static int MAX = 100001; static int []isPrime = new int[MAX]; static int sieve() { for (int p = 2; p * p < MAX; p++) { // If isPrime[p] is // not changed, then // it is a prime if (isPrime[p] == 0) { // Update all // multiples of p for (int i = p * 2; i < MAX; i += p) isPrime[i] = 1; } } return -1; } static int findSubset(int []a, int n) { int cnt1 = 0; // Counting no. of // ones in the array for (int i = 0; i < n; i++) if (a[i] == 1) cnt1++; // Case-I: count of // ones(1s) > 0 and // an integer > 1 is // present in the array if (cnt1 > 0) { for (int i = 0; i < n; i++) { // Find a[i], where // a[i] + 1 is prime. if ((a[i] != 1) && (isPrime[a[i] + 1] == 0)) { Console.WriteLine(cnt1 + 1); // Print all the ones(1s). for (int j = 0; j < cnt1; j++) Console.Write(1 + " "); Console.WriteLine(a[i]); // print a[i]. return 0; } } } // Case-II: array contains // only ones(1s) if (cnt1 >= 2) { Console.WriteLine(cnt1); // Print all ones(1s). for (int i = 0; i < cnt1; i++) Console.Write(1 + " "); Console.WriteLine(); return 0; } // Case-III: array does // not contain 1s for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Find a pair of integers // whose sum is prime if (isPrime[a[i] + a[j]] == 0) { Console.WriteLine(2); Console.WriteLine(a[i] + " " + a[j]); return 0; } } } // Array contains only // a single element. Console.WriteLine(-1); return -1; } // Driver Code static void Main() { sieve(); int []A = new int[]{ 2, 1, 1 }; int n = A.Length; findSubset(A, n); }}// This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php// PHP program to find // a subset in which // sum of every pair in// it is a prime$MAX = 100001;$isPrime = array(); for($i = 0; $i < $MAX; $i++) $isPrime[$i] = 0;function sieve(){ global $MAX, $isPrime; for ($p = 2; $p * $p < $MAX; $p++) { // If isPrime[p] is not // changed, then it is // a prime if ($isPrime[$p] == 0) { // Update all // multiples of p for ($i = $p * 2; $i < $MAX; $i += $p) $isPrime[$i] = 1; } }}function findSubset($a, $n){ $cnt1 = 0; global $MAX, $isPrime; // Counting no.of // ones in the array for ($i = 0; $i < $n; $i++) if ($a[$i] == 1) $cnt1++; // Case-I: count of // ones(1s) > 0 and // an integer > 1 is // present in the array if ($cnt1 > 0) { for ($i = 0; $i < $n; $i++) { // Find a[i], where // a[i] + 1 is prime. if (($a[$i] != 1) and ($isPrime[$a[$i] + 1] == 0)) { echo (($cnt1 + 1) . "\n"); // Print $all the ones(1s). for ($j = 0; $j < $cnt1; $j++) { echo ("1 "); } echo ($a[$i] . "\n"); return 0; } } } // Case-II: array contains // only ones(1s) if ($cnt1 >= 2) { echo (cnt1 . "\n"); // Print $all ones(1s). for ($i = 0; $i < $cnt1; $i++) echo ("1 "); echo ("\n"); return 0; } // Case-III: array does // not contain 1s for ($i = 0; $i < $n; $i++) { for ($j = $i + 1; $j < $n; $j++) { // Find a pair of integers // whose sum is prime if ($isPrime[$a[$i] + $a[$j]] == 0) { echo (2 . "\n"); echo ($a[$i] . " " . $a[$j] . "\n"); return 0; } } } // Array contains only // a single element. echo (-1 . "\n");}// Driver Codesieve();$A = array(2, 1, 1);$n = count($A);findSubset($A, $n);// This code is contributed by // Manish Shaw(manishshaw1)?> |
Javascript
<script>// JavaScript program to find a // subset in which sum of // every pair in it is a prime let MAX = 100001; let isPrime = new Array(MAX); for(let i=0;i<MAX;i++) { isPrime[i]=0; } function sieve() { for (let p = 2; p * p < MAX; p++) { // If isPrime[p] is // not changed, then // it is a prime if (isPrime[p] == 0) { // Update all // multiples of p for (let i = p * 2; i < MAX; i += p) isPrime[i] = 1; } } return -1; } function findSubset(a,n) { let cnt1 = 0; // Counting no. of // ones in the array for (let i = 0; i < n; i++) if (a[i] == 1) cnt1++; // Case-I: count of // ones(1s) > 0 and // an integer > 1 is // present in the array if (cnt1 > 0) { for (let i = 0; i < n; i++) { // Find a[i], where // a[i] + 1 is prime. if ((a[i] != 1) && (isPrime[a[i] + 1] == 0)) { document.write((cnt1 + 1)+"<br>"); // Print all // the ones(1s). for (let j = 0; j < cnt1; j++) document.write(1 + " "); // print a[i]. document.write(a[i]+"<br>"); return 0; } } } // Case-II: array contains // only ones(1s) if (cnt1 >= 2) { document.write(cnt1); // Print all ones(1s). for (let i = 0; i < cnt1; i++) document.write(1 + " "); document.write("<br>"); return 0; } // Case-III: array does // not contain 1s for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // Find a pair of integers // whose sum is prime if (isPrime[a[i] + a[j]] == 0) { document.write(2+"<br>"); document.write(a[i] + " " + a[j]+"<br>"); return 0; } } } // Array contains only // a single element. document.write(-1); return -1; } // Driver Code sieve(); let A=[2, 1, 1 ]; let n = A.length; findSubset(A, n);// This code is contributed by unknown2108</script> |
Output:
3 1 1 2
Time Complexity : O(n2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!