Given an array arr[] consisting of n distinct positive integers. Find the length of the largest subset in the given array which sums to a composite number and print the required array(order or printing elements does not matter).
Note: In case of multiple subsets with this largest size with the composite sum, output any of them.
Examples:
Input: arr[] = {8, 1, 4}, n=3
Output: 2, [8, 4]
Explanation: The required subset can be [8, 1] => 8 + 1 = 9 (composite number). Can also consider, [8, 4] (sum = 12 composite number). Note that [8, 1, 4] cannot be considered as it’s sum is not a composite number. Sum = 8 + 1 + 4 = 13(not a composite number).Input: arr[] = {6, 4, 2, 3}, n=4
Output: 4, [6, 2, 4, 3]
Explanation: Sum of all elements, = 6 + 4 + 2 + 3 = 15 (composite number), which is the largest subset.
Approach: The given problem can be solved easily by considering the fact that all even numbers sum to an even number (which will always be a composite number except 2) and then adding an odd number to that sum and checking whether the sum is composite or not. Follow the steps below to solve the problem:
- Create a temp[] vector, storing all the even numbers first and then the odd numbers present in the given array.
- Create a variable cursum, initialized to zero, to store the current sum of the temp array, variable maxlen = 0, to store the maximum length of composite sum.
- Iterate over the range [0, n) using the variable i and perform the following tasks:
- Add the value temp[i] to the variable currsum.
- If the value currrsum is a composite number and currsum is greater than maxlen then set the value of maxlen as i+1.
- After performing the above steps, print the value of maxlen as the answer and first maxlen elements from the array temp[] as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the current// sum is composite or notbool checkComposite(int n){ // 1 and 2 are not composite // number if (n == 1 || n == 2) { return false; } // If the number is divisible // by any digit except 2 and itself // then it's composite for (int i = 2; i < n; i++) { // If composite if (n % i == 0 && i != n) { return true; } } return false;}// Utility Function to find largest composite// subset sumvoid largestCompositeSum(int arr[], int n){ // Vector to store the elements of // arr in order of first even then // odd numbers vector<int> temp; // Even numbers pushed first in // temp array for (int i = 0; i < n; i++) { // Even check if (arr[i] % 2 == 0) { temp.push_back(arr[i]); } } // Odd numbers pushed for (int i = 0; i < n; i++) { // Odd check if (arr[i] % 2 == 1) { temp.push_back(arr[i]); } } // To store current sum int cursum = 0; // To store maximum length composite // sum int maxlen = 0; for (int i = 0; i < n; i++) { cursum += temp[i]; // If composite then update // cursum if (checkComposite(cursum) && cursum > maxlen) { maxlen = i + 1; } } cout << maxlen << endl; // Printing the required array for (int i = 0; i < maxlen; i++) { cout << temp[i] << " "; } return;}// Driver Codeint main(){ int n = 3; int arr[3] = { 8, 1, 4 }; // Function called largestCompositeSum(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to check if the current // sum is composite or not static boolean checkComposite(int n) { // 1 and 2 are not composite // number if (n == 1 || n == 2) { return false; } // If the number is divisible // by any digit except 2 and itself // then it's composite for (int i = 2; i < n; i++) { // If composite if (n % i == 0 && i != n) { return true; } } return false; } // Utility Function to find largest composite // subset sum static void largestCompositeSum(int arr[], int n) { // Vector to store the elements of // arr in order of first even then // odd numbers Vector<Integer> temp = new Vector<Integer>(); // Even numbers pushed first in // temp array for (int i = 0; i < n; i++) { // Even check if (arr[i] % 2 == 0) { temp.add(arr[i]); } } // Odd numbers pushed for (int i = 0; i < n; i++) { // Odd check if (arr[i] % 2 == 1) { temp.add(arr[i]); } } // To store current sum int cursum = 0; // To store maximum length composite // sum int maxlen = 0; for (int i = 0; i < n; i++) { cursum += temp.get(i); // If composite then update // cursum if (checkComposite(cursum) && cursum > maxlen) { maxlen = i + 1; } } System.out.print(maxlen +"\n"); // Printing the required array for (int i = 0; i < maxlen; i++) { System.out.print(temp.get(i)+ " "); } return; } // Driver Code public static void main(String[] args) { int n = 3; int arr[] = { 8, 1, 4 }; // Function called largestCompositeSum(arr, n); }}// This code is contributed by shikhasingrajput |
Python
# Python program for the above approach# Function to check if the current# sum is composite or notdef checkComposite(n): # 1 and 2 are not composite # number if (n == 1 or n == 2): return false # If the number is divisible # by any digit except 2 and itself # then it's composite for i in range(2, n): # If composite if (n % i == 0 and i != n): return True return False# Utility Function to find largest composite# subset sumdef largestCompositeSum(arr, n): # Vector to store the elements of # arr in order of first even then # odd numbers temp = [] # Even numbers pushed first in # temp array for i in range(n): # Even check if (arr[i] % 2 == 0): temp.append(arr[i]) # Odd numbers pushed for i in range(n): # Odd check if (arr[i] % 2 == 1): temp.append(arr[i]) # To store current sum cursum = 0; # To store maximum length composite # sum maxlen = 0; for i in range(n): cursum += temp[i] # If composite then update # cursum if (checkComposite(cursum) and cursum > maxlen): maxlen = i + 1 print(maxlen) l = len(temp) - maxlen for i in range(l): temp.remove(temp[i + maxlen]) # Printing the required array print(*temp) return# Driver coden = 3arr = [8, 1, 4]# Function calledlargestCompositeSum(arr, n);# This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if the current // sum is composite or not static bool checkComposite(int n) { // 1 and 2 are not composite // number if (n == 1 || n == 2) { return false; } // If the number is divisible // by any digit except 2 and itself // then it's composite for (int i = 2; i < n; i++) { // If composite if (n % i == 0 && i != n) { return true; } } return false; } // Utility Function to find largest composite // subset sum static void largestCompositeSum(int[] arr, int n) { // Vector to store the elements of // arr in order of first even then // odd numbers List<int> temp = new List<int>(); // Even numbers pushed first in // temp array for (int i = 0; i < n; i++) { // Even check if (arr[i] % 2 == 0) { temp.Add(arr[i]); } } // Odd numbers pushed for (int i = 0; i < n; i++) { // Odd check if (arr[i] % 2 == 1) { temp.Add(arr[i]); } } // To store current sum int cursum = 0; // To store maximum length composite // sum int maxlen = 0; for (int i = 0; i < n; i++) { cursum += temp[i]; // If composite then update // cursum if (checkComposite(cursum) && cursum > maxlen) { maxlen = i + 1; } } Console.WriteLine(maxlen); // Printing the required array for (int i = 0; i < maxlen; i++) { Console.Write(temp[i] + " "); } return; } // Driver Code public static void Main() { int n = 3; int[] arr = { 8, 1, 4 }; // Function called largestCompositeSum(arr, n); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to check if the current // sum is composite or not function checkComposite(n) { // 1 and 2 are not composite // number if (n == 1 || n == 2) { return false; } // If the number is divisible // by any digit except 2 and itself // then it's composite for (let i = 2; i < n; i++) { // If composite if (n % i == 0 && i != n) { return true; } } return false; } // Utility Function to find largest composite // subset sum function largestCompositeSum(arr, n) { // Vector to store the elements of // arr in order of first even then // odd numbers let temp = []; // Even numbers pushed first in // temp array for (let i = 0; i < n; i++) { // Even check if (arr[i] % 2 == 0) { temp.push(arr[i]); } } // Odd numbers pushed for (let i = 0; i < n; i++) { // Odd check if (arr[i] % 2 == 1) { temp.push(arr[i]); } } // To store current sum let cursum = 0; // To store maximum length composite // sum let maxlen = 0; for (let i = 0; i < n; i++) { cursum += temp[i]; // If composite then update // cursum if (checkComposite(cursum) && cursum > maxlen) { maxlen = i + 1; } } document.write(maxlen + '<br>'); // Printing the required array for (let i = 0; i < maxlen; i++) { document.write(temp[i] + " "); } return; } // Driver Code let n = 3; let arr = [8, 1, 4]; // Function called largestCompositeSum(arr, n); // This code is contributed by Potta Lokesh </script> |
Output:
2 8 4
Time Complexity: O(n2)
Auxiliary Space: O(n), required for temp array.
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!