Sum and product of k smallest and k largest composite numbers in the array
Given an integer k and an array of integers arr, the task is to find the sum and product of k smallest and k largest composite numbers in the array.
Assume that there are at least k composite numbers in the array.
Examples:
Input: arr[] = {2, 5, 6, 8, 10, 11}, k = 2
Output: Sum of k-minimum composite numbers is 14
Sum of k-maximum composite numbers is 18
Product of k-minimum composite numbers is 48
Product of k-maximum composite numbers is 80
{6, 8, 10} are the only composite numbers from the array. {6, 8} are the 2 smallest and {8, 10} are the 2 largest among them.Input: arr[] = {6, 4, 2, 12, 13, 5, 19, 10}, k = 3
Output: Sum of k-minimum composite numbers is 20
Sum of k-maximum composite numbers is 28
Product of k-minimum composite numbers is 240
Product of k-maximum composite numbers is 720
Approach:
- Using Sieve of Eratosthenes generate a boolean vector upto the size of the maximum element from the array which can be used to check whether a number is composite or not.
- Also set 0 and 1 as prime so that they don’t get counted as composite numbers.
- Now traverse the array and insert all the numbers which are composite in two heaps, a min heap and a max heap.
- Now, pop out top k elements from the min heap and take the sum and product of the minimum k composite numbers.
- Do the same with the max heap to get the sum and product of the max k composite numbers.
- Finally, print the results.
Below is the implementation of the above approach:
C++
// C++ program to find the sum and // product of k smallest and k largest // composite numbers in an array #include <bits/stdc++.h> using namespace std; vector< bool > SieveOfEratosthenes( int max_val) { // Create a boolean vector "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. vector< bool > prime(max_val + 1, true ); for ( int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i = p * 2; i <= max_val; i += p) prime[i] = false ; } } return prime; } // Function that calculates the sum // and product of k smallest and k // largest composite numbers in an array void compositeSumAndProduct( int arr[], int n, int k) { // Find maximum value in the array int max_val = *max_element(arr, arr + n); // Use sieve to find all prime numbers // less than or equal to max_val vector< bool > prime = SieveOfEratosthenes(max_val); // Set 0 and 1 as primes so that // they don't get counted as // composite numbers prime[0] = true ; prime[1] = true ; // Max Heap to store all the composite numbers priority_queue< int > maxHeap; // Min Heap to store all the composite numbers priority_queue< int , vector< int >, greater< int >> minHeap; // Push all the composite numbers // from the array to the heaps for ( int i = 0; i < n; i++) if (!prime[arr[i]]) { minHeap.push(arr[i]); maxHeap.push(arr[i]); } long long int minProduct = 1 , maxProduct = 1 , minSum = 0 , maxSum = 0; while (k--) { // Calculate the products minProduct *= minHeap.top(); maxProduct *= maxHeap.top(); // Calculate the sum minSum += minHeap.top(); maxSum += maxHeap.top(); // Pop the current minimum element minHeap.pop(); // Pop the current maximum element maxHeap.pop(); } cout << "Sum of k-minimum composite numbers is " << minSum << "\n" ; cout << "Sum of k-maximum composite numbers is " << maxSum << "\n" ; cout << "Product of k-minimum composite numbers is " << minProduct << "\n" ; cout << "Product of k-maximum composite numbers is " << maxProduct; } // Driver code int main() { int arr[] = { 4, 2, 12, 13, 5, 19 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 3; compositeSumAndProduct(arr, n, k); return 0; } |
Java
// Java program to find the sum and // product of k smallest and k largest // composite numbers in an array import java.util.*; class GFG { static boolean [] SieveOfEratosThenes( int max_val) { // Create a boolean vector "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. boolean [] prime = new boolean [max_val + 1 ]; Arrays.fill(prime, true ); for ( int p = 2 ; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p]) { // Update all multiples of p for ( int i = p * 2 ; i <= max_val; i += p) prime[i] = false ; } } return prime; } // Function that calculates the sum // and product of k smallest and k // largest composite numbers in an array static void compositeSumAndProduct(Integer[] arr, int n, int k) { // Find maximum value in the array int max_val = Collections.max(Arrays.asList(arr)); // Use sieve to find all prime numbers // less than or equal to max_val boolean [] prime = SieveOfEratosThenes(max_val); // Set 0 and 1 as primes so that // they don't get counted as // composite numbers prime[ 0 ] = true ; prime[ 1 ] = true ; // Max Heap to store all the composite numbers PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((x, y) -> y - x); // Min Heap to store all the composite numbers PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Push all the composite numbers // from the array to the heaps for ( int i = 0 ; i < n; i++) { if (!prime[arr[i]]) { minHeap.add(arr[i]); maxHeap.add(arr[i]); } } long minProduct = 1 , maxProduct = 1 , minSum = 0 , maxSum = 0 ; Integer lastMin = 0 , lastMax = 0 ; while (k-- > 0 ) { if (minHeap.peek() != null || maxHeap.peek() != null ) { // Calculate the products minProduct *= minHeap.peek(); maxProduct *= maxHeap.peek(); // Calculate the sum minSum += minHeap.peek(); maxSum += maxHeap.peek(); // Pop the current minimum element lastMin = minHeap.poll(); // Pop the current maximum element lastMax = maxHeap.poll(); } else { // when maxHeap or minHeap is exhausted // then this condition will run minProduct *= lastMin; maxProduct *= lastMax; minSum += lastMin; maxSum += lastMax; } } System.out.println( "Sum of k-minimum composite" + " numbers is " + minSum); System.out.println( "Sum of k-maximum composite" + " numbers is " + maxSum); System.out.println( "Product of k-minimum composite" + " numbers is " + minProduct); System.out.println( "Product of k-maximum composite" + " numbers is " + maxProduct); } // Driver Code public static void main(String[] args) { Integer[] arr = { 4 , 2 , 12 , 13 , 5 , 19 }; int n = arr.length; int k = 3 ; compositeSumAndProduct(arr, n, k); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to find the sum and # product of k smallest and k largest # composite numbers in an array def SieveOfEratosthenes(max_val): # Create a boolean vector "prime[0..n]". A # value in prime[i] will finally be false # if i is Not a prime, else true. prime = [ True for _ in range (max_val + 1 )] for p in range ( 2 , 1 + int (max_val * * 0.5 )): # If prime[p] is not changed, then # it is a prime if prime[p]: # Update all multiples of p for i in range ( 2 * p, max_val + 1 , p): prime[i] = False return prime # Function that calculates the sum # and product of k smallest and k # largest composite numbers in an array def compositeSumAndProduct(arr, n, k): # Find maximum value in the array max_val = max (arr) # Use sieve to find all prime numbers # less than or equal to max_val prime = SieveOfEratosthenes(max_val) # Set 0 and 1 as primes so that # they don't get counted as # composite numbers prime[ 0 ] = True prime[ 1 ] = True # Max Heap to store all the composite numbers maxHeap = [] # Min Heap to store all the composite numbers minHeap = [] # Push all the composite numbers # from the array to the heaps for i in range (n): if not prime[arr[i]]: minHeap.append(arr[i]) maxHeap.append(arr[i]) minHeap.sort() maxHeap.sort(reverse = True ) minProduct = 1 maxProduct = 1 minSum = 0 maxSum = 0 lastMin = 0 lastMax = 0 while k > 0 : if minHeap and maxHeap: # Calculate the products minProduct * = minHeap[ 0 ] maxProduct * = maxHeap[ 0 ] # Calculate the sum minSum + = minHeap[ 0 ] maxSum + = maxHeap[ 0 ] # Pop the current minimum element lastMin = minHeap.pop( 0 ) # Pop the current maximum element lastMax = maxHeap.pop( 0 ) else : minProduct * = lastMin maxProduct * = lastMax minSum + = lastMin maxSum + = lastMax k - = 1 print ( "Sum of k-minimum composite numbers is" , minSum) print ( "Sum of k-maximum composite numbers is" , maxSum) print ( "Product of k-minimum composite numbers is" , minProduct) print ( "Product of k-maximum composite numbers is" , maxProduct) # Driver code arr = [ 4 , 2 , 12 , 13 , 5 , 19 ] n = len (arr) k = 3 compositeSumAndProduct(arr, n, k) # This code is contributed by phasing17 |
C#
// C# program to find the sum and // product of k smallest and k largest // composite numbers in an array using System; using System.Linq; using System.Collections.Generic; class GFG { static bool [] SieveOfEratosThenes( int max_val) { // Create a boolean vector "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. bool [] prime = new bool [max_val + 1]; for ( int i = 0; i <= max_val; i++) prime[i] = true ; for ( int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p]) { // Update all multiples of p for ( int i = p * 2; i <= max_val; i += p) prime[i] = false ; } } return prime; } // Function that calculates the sum // and product of k smallest and k // largest composite numbers in an array static void compositeSumAndProduct( int [] arr, int n, int k) { // Find maximum value in the array int max_val = arr.Max(); // Use sieve to find all prime numbers // less than or equal to max_val bool [] prime = SieveOfEratosThenes(max_val); // Set 0 and 1 as primes so that // they don't get counted as // composite numbers prime[0] = true ; prime[1] = true ; // Max Heap to store all the composite numbers List< int > maxHeap = new List< int >(); // Min Heap to store all the composite numbers List< int > minHeap = new List< int >(); // Push all the composite numbers // from the array to the heaps for ( int i = 0; i < n; i++) { if (!prime[arr[i]]) { minHeap.Add(arr[i]); maxHeap.Add(arr[i]); } } minHeap = minHeap.OrderBy(a => a).ToList(); maxHeap = maxHeap.OrderBy(a => -a).ToList(); long minProduct = 1, maxProduct = 1, minSum = 0, maxSum = 0; int lastMin = 0, lastMax = 0; while (k-- > 0) { if (minHeap.Count != 0 || maxHeap.Count != 0) { // Calculate the products minProduct *= minHeap[0]; maxProduct *= maxHeap[0]; // Calculate the sum minSum += minHeap[0]; maxSum += maxHeap[0]; // Pop the current minimum element lastMin = minHeap[0]; minHeap.RemoveAt(0); // Pop the current maximum element lastMax = maxHeap[0]; maxHeap.RemoveAt(0); } else { // when maxHeap or minHeap is exhausted // then this condition will run minProduct *= lastMin; maxProduct *= lastMax; minSum += lastMin; maxSum += lastMax; } } Console.WriteLine( "Sum of k-minimum composite" + " numbers is " + minSum); Console.WriteLine( "Sum of k-maximum composite" + " numbers is " + maxSum); Console.WriteLine( "Product of k-minimum composite" + " numbers is " + minProduct); Console.WriteLine( "Product of k-maximum composite" + " numbers is " + maxProduct); } // Driver Code public static void Main( string [] args) { int [] arr = { 4, 2, 12, 13, 5, 19 }; int n = arr.Length; int k = 3; compositeSumAndProduct(arr, n, k); } } // This code is contributed by // phasing17 |
Javascript
// JS program to find the sum and // product of k smallest and k largest // composite numbers in an array function SieveOfEratosthenes(max_val) { // Create a boolean vector "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. let prime = new Array(max_val + 1).fill( true ); for ( var p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true ) { // Update all multiples of p for ( var i = p * 2; i <= max_val; i += p) prime[i] = false ; } } return prime; } // Function that calculates the sum // and product of k smallest and k // largest composite numbers in an array function compositeSumAndProduct(arr, n, k) { // Find maximum value in the array let max_val = Math.max(...arr) // Use sieve to find all prime numbers // less than or equal to max_val let prime = SieveOfEratosthenes(max_val); // Set 0 and 1 as primes so that // they don't get counted as // composite numbers prime[0] = true ; prime[1] = true ; // Max Heap to store all the composite numbers let maxHeap = []; // Min Heap to store all the composite numbers let minHeap = []; // Push all the composite numbers // from the array to the heaps for ( var i = 0; i < n; i++) if (!prime[arr[i]]) { minHeap.push(arr[i]); maxHeap.push(arr[i]); } minHeap.sort( function (a, b) { return a > b}); maxHeap.sort( function (a, b) { return a < b}); let minProduct = 1 , maxProduct = 1 , minSum = 0 , maxSum = 0; while (k-- > 0) { // Calculate the products minProduct *= minHeap[0]; maxProduct *= maxHeap[0]; // Calculate the sum minSum += minHeap[0]; maxSum += maxHeap[0]; // Pop the current minimum element minHeap.shift(); // Pop the current maximum element maxHeap.shift(); } console.log( "Sum of k-minimum composite numbers is " + minSum) console.log( "Sum of k-maximum composite numbers is " + maxSum); console.log( "Product of k-minimum composite numbers is " + minProduct); console.log( "Product of k-maximum composite numbers is " + maxProduct); } // Driver code let arr = [ 6, 4, 2, 12, 13, 5, 19, 10]; let n = arr.length; let k = 3; compositeSumAndProduct(arr, n, k); // This code is contributed by phasing17 |
Sum of k-minimum composite numbers is 28 Sum of k-maximum composite numbers is 20 Product of k-minimum composite numbers is 576 Product of k-maximum composite numbers is 192
Approach: Heap-based Selection of K-Smallest and K-Largest Composite Numbers
Here are the steps for the “Heap-based Selection of K-Smallest and K-Largest Composite Numbers” approach:
- Define a function is_composite(n) that takes an integer n as input and returns True if n is composite, i.e., if it has a factor other than 1 and itself.
- Define a function sum_product_k_smallest_largest_composite(arr, k) that takes an array of integers arr and an integer k as inputs and returns a tuple containing the sum and product of the k smallest and k largest composite numbers in arr.
- Initialize an empty list composite_nums.
- Iterate over the integers in arr, and for each integer num, check if it is composite using the is_composite() function. If num is composite, append it to the composite_nums list.
- Use the heapq.nsmallest(k, composite_nums) function to find the k smallest composite numbers in composite_nums. Assign the result to a variable k_smallest_composites.
- Use the heapq.nlargest(k, composite_nums) function to find the k largest composite numbers in composite_nums. Assign the result to a variable k_largest_composites.
- Calculate the sum of the k smallest composite numbers in k_smallest_composites, and assign the result to a variable sum_k_smallest.
- Calculate the sum of the k largest composite numbers in k_largest_composites, and assign the result to a variable sum_k_largest.
Initialize variables product_k_smallest and product_k_largest to 1. - Iterate over the integers in k_smallest_composites, and for each integer num, multiply it with product_k_smallest.
- Iterate over the integers in k_largest_composites, and for each integer num, multiply it with product_k_largest.
- Return a tuple containing sum_k_smallest, sum_k_largest, product_k_smallest, and product_k_largest.
Java
// Java equivalent of the above code import java.util.PriorityQueue; public class SumProductKSmallestLargestComposite { public static boolean isComposite( int n) { if (n < 2 ) { return false ; } for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { return true ; } } return false ; } public static int [] sumProductKSmallestLargestComposite( int [] arr, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a)); for ( int num : arr) { if (isComposite(num)) { minHeap.add(num); maxHeap.add(num); } } int sumKSmallest = 0 ; int sumKLargest = 0 ; int productKSmallest = 1 ; int productKLargest = 1 ; for ( int i = 0 ; i < k; i++) { sumKSmallest += minHeap.peek(); sumKLargest += maxHeap.peek(); productKSmallest *= minHeap.poll(); productKLargest *= maxHeap.poll(); } return new int [] {sumKSmallest, sumKLargest, productKSmallest, productKLargest}; } public static void main(String[] args) { int [] arr = { 6 , 4 , 2 , 12 , 13 , 5 , 19 , 10 }; int k = 3 ; int [] result = sumProductKSmallestLargestComposite(arr, k); System.out.println( "Sum of k-minimum composite numbers: " + result[ 0 ]); System.out.println( "Sum of k-maximum composite numbers: " + result[ 1 ]); System.out.println( "Product of k-minimum composite numbers: " + result[ 2 ]); System.out.println( "Product of k-maximum composite numbers: " + result[ 3 ]); } } |
Python3
import heapq from math import sqrt def is_composite(n): if n < 2 : return False for i in range ( 2 , int (sqrt(n)) + 1 ): if n % i = = 0 : return True return False def sum_product_k_smallest_largest_composite(arr, k): composite_nums = [] for num in arr: if is_composite(num): composite_nums.append(num) k_smallest_composites = heapq.nsmallest(k, composite_nums) k_largest_composites = heapq.nlargest(k, composite_nums) sum_k_smallest = sum (k_smallest_composites) sum_k_largest = sum (k_largest_composites) product_k_smallest = 1 product_k_largest = 1 for num in k_smallest_composites: product_k_smallest * = num for num in k_largest_composites: product_k_largest * = num return (sum_k_smallest, sum_k_largest, product_k_smallest, product_k_largest) arr = [ 6 , 4 , 2 , 12 , 13 , 5 , 19 , 10 ] k = 3 result = sum_product_k_smallest_largest_composite(arr, k) print ( "Sum of k-minimum composite numbers:" , result[ 0 ]) print ( "Sum of k-maximum composite numbers:" , result[ 1 ]) print ( "Product of k-minimum composite numbers:" , result[ 2 ]) print ( "Product of k-maximum composite numbers:" , result[ 3 ]) |
Javascript
function is_composite(n) { if (n < 2) { return false ; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return true ; } } return false ; } function sum_product_k_smallest_largest_composite(arr, k) { let composite_nums = []; for (let num of arr) { if (is_composite(num)) { composite_nums.push(num); } } let k_smallest_composites = composite_nums.slice(0).sort((a, b) => a - b).slice(0, k); let k_largest_composites = composite_nums.slice(0).sort((a, b) => b - a).slice(0, k); let sum_k_smallest = k_smallest_composites.reduce((a, b) => a + b, 0); let sum_k_largest = k_largest_composites.reduce((a, b) => a + b, 0); let product_k_smallest = k_smallest_composites.reduce((a, b) => a * b, 1); let product_k_largest = k_largest_composites.reduce((a, b) => a * b, 1); return [sum_k_smallest, sum_k_largest, product_k_smallest, product_k_largest]; } let arr = [6, 4, 2, 12, 13, 5, 19, 10]; let k = 3; let result = sum_product_k_smallest_largest_composite(arr, k); console.log( "Sum of k-minimum composite numbers:" , result[0]); console.log( "Sum of k-maximum composite numbers:" , result[1]); console.log( "Product of k-minimum composite numbers:" , result[2]); console.log( "Product of k-maximum composite numbers:" , result[3]); |
C++
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cmath> using namespace std; bool isComposite( int n) { if (n < 2) { return false ; } for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) { return true ; } } return false ; } vector< int > sumProductKSmallestLargestComposite(vector< int > arr, int k) { priority_queue< int , vector< int >, greater< int >> minHeap; priority_queue< int , vector< int >, less< int >> maxHeap; for ( int num : arr) { if (isComposite(num)) { minHeap.push(num); maxHeap.push(num); } } int sumKSmallest = 0; int sumKLargest = 0; int productKSmallest = 1; int productKLargest = 1; for ( int i = 0; i < k; i++) { sumKSmallest += minHeap.top(); sumKLargest += maxHeap.top(); productKSmallest *= minHeap.top(); productKLargest *= maxHeap.top(); minHeap.pop(); maxHeap.pop(); } return {sumKSmallest, sumKLargest, productKSmallest, productKLargest}; } int main() { vector< int > arr = {6, 4, 2, 12, 13, 5, 19, 10}; int k = 3; vector< int > result = sumProductKSmallestLargestComposite(arr, k); cout << "Sum of k-minimum composite numbers: " << result[0] << endl; cout << "Sum of k-maximum composite numbers: " << result[1] << endl; cout << "Product of k-minimum composite numbers: " << result[2] << endl; cout << "Product of k-maximum composite numbers: " << result[3] << endl; return 0; } |
C#
using System; using System.Collections.Generic; using System.Linq; public class Program { // Function to check if a number n is // composite or not public static bool IsComposite( int n) { if (n < 2) { return false ; } for ( int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return true ; } } return false ; } // Function to find the sum and product // of K smallest and largest composite public static List< int > SumProductKSmallestLargestComposite(List< int > arr, int k) { List< int > compositeNums = new List< int >(); foreach ( int num in arr) { if (IsComposite(num)) { compositeNums.Add(num); } } List< int > kSmallestComposites = compositeNums.OrderBy(x = > x) .Take(k) .ToList(); List< int > kLargestComposites = compositeNums.OrderByDescending(x = > x) .Take(k) .ToList(); int sumKSmallest = kSmallestComposites.Sum(); int sumKLargest = kLargestComposites.Sum(); int productKSmallest = kSmallestComposites.Aggregate((x, y) = > x * y); int productKLargest = kLargestComposites.Aggregate( (x, y) = > x * y); return new List< int >{ sumKSmallest, sumKLargest, productKSmallest, productKLargest }; } // Driver Code public static void Main() { List< int > arr = new List< int >{ 6, 4, 2, 12, 13, 5, 19, 10 }; int k = 3; List< int > result = SumProductKSmallestLargestComposite(arr, k); Console.WriteLine( "Sum of k-minimum composite numbers: " + result[0]); Console.WriteLine( "Sum of k-maximum composite numbers: " + result[1]); Console.WriteLine( "Product of k-minimum composite numbers: " + result[2]); Console.WriteLine( "Product of k-maximum composite numbers: " + result[3]); } } |
Sum of k-minimum composite numbers: 20 Sum of k-maximum composite numbers: 28 Product of k-minimum composite numbers: 240 Product of k-maximum composite numbers: 720
Time Complexity: O(n * sqrt(max(arr)) + k * log(n))
Auxiliary Space: O(n + k)
Contact Us