Largest subset with sum of every pair as prime
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 100001 bool 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 function int 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 prime import 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 prime import math as mt MAX = 100001 isPrime = [ 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] = 1 def 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 Code sieve() 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 prime using 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 Code sieve(); $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)
Contact Us