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 prime numbers in the array.
Assume that there are at least k prime numbers in the array.
Examples:
Input: arr[] = {2, 5, 6, 8, 10, 11}, k = 2
Output: Sum of k-minimum prime numbers is 7
Sum of k-maximum prime numbers is 16
Product of k-minimum prime numbers is 10
Product of k-maximum prime numbers is 55
{2, 5, 11} are the only prime numbers from the array. {2, 5} are the 2 smallest and {5, 11} are the 2 largest among them.Input: arr[] = {4, 2, 12, 13, 5, 19}, k = 3
Output: Sum of k-minimum prime numbers is 20
Sum of k-maximum prime numbers is 37
Product of k-minimum prime numbers is 130
Product of k-maximum prime numbers is 1235
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 prime or not.
- Also set 0 and 1 as non-prime so that they don’t get counted as prime numbers.
- Now traverse the array and insert all the numbers which are prime 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 prime numbers.
- Do the same with the max heap to get the sum and product of the max k prime 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 prime 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 prime numbers in an arrayvoid primeSumAndProduct(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 non-primes as // they don't need to be // counted as prime numbers prime[0] = false; prime[1] = false; // Max Heap to store all the prime numbers priority_queue<int> maxHeap; // Min Heap to store all the prime numbers priority_queue<int, vector<int>, greater<int>> minHeap; // Push all the prime 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 prime numbers is " << minSum << "\n"; cout << "Sum of k-maximum prime numbers is " << maxSum << "\n"; cout << "Product of k-minimum prime numbers is " << minProduct << "\n"; cout << "Product of k-maximum prime numbers is " << maxProduct;}// Driver codeint main(){ int arr[] = { 4, 2, 12, 13, 5, 19 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 3; primeSumAndProduct(arr, n, k); return 0;} |
Java
// Java program to find the sum // and product of k smallest and // k largest prime numbers in an array import java.util.*;class GFG { public static void main(String[] args) { int arr[] = { 4, 2, 12, 13, 5, 19 }; int n = arr.length; int k = 3; primeSumAndProduct(arr, n, k); } 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]; 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] == 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 prime numbers in an array static void primeSumAndProduct(int arr[], int n, int k) { // Find maximum value in the array int max_val = 0; for (int i = 0; i < n; i++) max_val = Math.max(max_val, arr[i]); // Use sieve to find all prime numbers // less than or equal to max_val boolean[] prime = SieveOfEratosthenes(max_val); // Set 0 and 1 as non-primes as // they don't need to be // counted as prime numbers prime[0] = false; prime[1] = false; // Max Heap to store all the prime numbers PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); // Min Heap to store all the prime numbers PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); // Push all the prime 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; while (k > 0) { k--; // Calculate the products minProduct *= minHeap.peek(); maxProduct *= maxHeap.peek(); // Calculate the sum minSum += minHeap.peek(); maxSum += maxHeap.peek(); // Pop the current minimum element minHeap.remove(); // Pop the current maximum element maxHeap.remove(); } System.out.println("Sum of k-minimum prime numbers is " + minSum); System.out.println("Sum of k-maximum prime numbers is " + maxSum); System.out.println("Product of k-minimum prime numbers is " + minProduct); System.out.println("Product of k-maximum prime numbers is " + maxProduct); }}// This code is contributed by ankush_953 |
Python3
# Python program to find the sum # and product of k smallest and # k largest prime numbers in an array import heapqdef 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 i in range(max_val+1)] p = 2 while p*p <= max_val: # If prime[p] is not changed, then # it is a prime if (prime[p] == True): # Update all multiples of p for j in range(2*p,max_val+1,p): prime[j] = False p += 1 return prime# Function that calculates the sum # and product of k smallest and k # largest prime numbers in an array def primeSumAndProduct(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 non-primes as # they don't need to be # counted as prime numbers prime[0] = False prime[1] = False # Heap to store all the prime numbers Heap = [] # Push all the prime numbers # from the array to the heaps for i in range(n): if (prime[arr[i]]): Heap.append(arr[i]) minProduct = 1 maxProduct = 1 minSum = 0 maxSum = 0 min_k = heapq.nsmallest(k,Heap) max_k = heapq.nlargest(k,Heap) minSum = sum(min_k) maxSum = sum(max_k) for val in min_k: minProduct *= val for val in max_k: maxProduct *= val print("Sum of k-minimum prime numbers is", minSum) print("Sum of k-maximum prime numbers is", maxSum) print("Product of k-minimum prime numbers is", minProduct) print("Product of k-maximum prime numbers is", maxProduct) # Driver code arr = [ 4, 2, 12, 13, 5, 19 ]n = len(arr)k = 3primeSumAndProduct(arr, n, k)# This code is contributed by ankush_953 |
C#
// C# program to find the sum// and product of k smallest and// k largest prime numbers in an arrayusing System;using System.Collections.Generic;class GFG { public static void Main(string[] args) { int[] arr = { 4, 2, 12, 13, 5, 19 }; int n = arr.Length; int k = 3; primeSumAndProduct(arr, n, k); } 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] == 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 prime numbers in an array static void primeSumAndProduct(int[] arr, int n, int k) { // Find maximum value in the array int max_val = 0; for (int i = 0; i < n; i++) max_val = Math.Max(max_val, arr[i]); // Use sieve to find all prime numbers // less than or equal to max_val bool[] prime = SieveOfEratosthenes(max_val); // Set 0 and 1 as non-primes as // they don't need to be // counted as prime numbers prime[0] = false; prime[1] = false; // Max Heap to store all the prime numbers List<int> maxHeap = new List<int>(); // Min Heap to store all the prime numbers List<int> minHeap = new List<int>(); // Push all the prime 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.Sort(); maxHeap.Sort(); maxHeap.Reverse(); long minProduct = 1, maxProduct = 1, minSum = 0, maxSum = 0; while (k > 0) { k--; // Calculate the products minProduct *= minHeap[0]; maxProduct *= maxHeap[0]; // Calculate the sum minSum += minHeap[0]; maxSum += maxHeap[0]; // Pop the current minimum element minHeap.RemoveAt(0); // Pop the current maximum element maxHeap.RemoveAt(0); } Console.WriteLine( "Sum of k-minimum prime numbers is " + minSum); Console.WriteLine( "Sum of k-maximum prime numbers is " + maxSum); Console.WriteLine( "Product of k-minimum prime numbers is " + minProduct); Console.WriteLine( "Product of k-maximum prime numbers is " + maxProduct); }}// This code is contributed by phasing17 |
Javascript
// JS program to find the sum // and product of k smallest and // k largest prime 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) let p = 2 while (p*p <= max_val) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true) { // Update all multiples of p for (var j = 2 * p; j <= max_val; j += p) prime[j] = false } p += 1 } return prime}// Function that calculates the sum // and product of k smallest and k // largest prime numbers in an array function primeSumAndProduct(arr, n, k){ // Find maximum value in the array let max_val = Math.max.apply(null, 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 non-primes as // they don't need to be // counted as prime numbers prime[0] = false prime[1] = false // Heap to store all the prime numbers let Heap = [] // Push all the prime numbers // from the array to the heaps for (var i = 0; i < n; i++) { if (prime[arr[i]]) Heap.push(arr[i]) } let minProduct = 1 let maxProduct = 1 Heap.sort(function(a, b) { return a > b }) // Storing the k minimum prime numbers let min_k = [...Heap.slice(0, k)] Heap.reverse() // Storing the k maximum prime numbers let max_k = [...Heap.slice(0, k)] // Calculating the sum of k-minimum prime numbers let minSum = 0 for (var val of min_k) minSum += val // Calculating the sum of k-maximum prime numbers let maxSum = 0 for (var val of max_k) maxSum += val // Calculating the product of k - minimum prime numbers for (var val of min_k) minProduct *= val // Calculating the product of k - maximum prime numbers for (var val of max_k) maxProduct *= val // Displaying the results console.log("Sum of k-minimum prime numbers is", minSum) console.log("Sum of k-maximum prime numbers is", maxSum) console.log("Product of k-minimum prime numbers is", minProduct) console.log("Product of k-maximum prime numbers is", maxProduct) }// Driver code let arr = [ 4, 2, 12, 13, 5, 19 ]let n = (arr).lengthlet k = 3primeSumAndProduct(arr, n, k)// This code is contributed by phasing17 |
Output
Sum of k-minimum prime numbers is 20 Sum of k-maximum prime numbers is 37 Product of k-minimum prime numbers is 130 Product of k-maximum prime numbers is 1235
Complexity Analysis:
- Time Complexity: O(N*log(N) + max_val * log(log(max_val)) ) Where N is the total number of elements and max_val is the maximum value in the array.
- Auxiliary Space: O(N + max_val)
Approach 2(hash table): We can create a hash table to store all the prime numbers in the array. We can iterate over each element in the array and check if it is a prime number. If an element is prime, we can add it to the hash table.
Algorithm steps:
- Create an empty unordered_map to keep track of prime numbers found in the input array.
- Traverse the input array and for each number, use the is_prime function to determine whether it is a prime number.
- If a prime number is found, add it to the unordered_map.
- Once all numbers in the input array have been checked, extract the values of the unordered_map into a vector.
- Sort the vector of primes in ascending order.
- Create two empty vectors to store the k smallest and k largest primes, respectively.
- Use the std::partial_sort function to extract the k smallest and k largest primes from the sorted vector.
- Compute the sum and product of the k smallest and k largest primes, respectively.
- Return a tuple containing the sum and product of the k smallest and k largest primes.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <algorithm>#include <cmath>#include <iostream>#include <numeric>#include <unordered_map>#include <vector>using namespace std;bool is_prime(int n){ if (n < 2) { return false; } for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true;}tuple<int, int, int, int>sum_and_product_of_k_primes(vector<int>& arr, int k){ unordered_map<int, bool> primes; for (int p : arr) { if (is_prime(p)) { primes[p] = true; } } vector<int> sorted_primes; for (auto it = primes.begin(); it != primes.end(); it++) { sorted_primes.push_back(it->first); } sort(sorted_primes.begin(), sorted_primes.end()); vector<int> k_smallest_primes( sorted_primes.begin(), sorted_primes.begin() + k); sort(sorted_primes.rbegin(), sorted_primes.rend()); vector<int> k_largest_primes(sorted_primes.begin(), sorted_primes.begin() + k); int sum_k_smallest = accumulate(k_smallest_primes.begin(), k_smallest_primes.end(), 0); int sum_k_largest = accumulate(k_largest_primes.begin(), k_largest_primes.end(), 0); int product_k_smallest = accumulate( k_smallest_primes.begin(), k_smallest_primes.end(), 1, multiplies<int>()); int product_k_largest = accumulate( k_largest_primes.begin(), k_largest_primes.end(), 1, multiplies<int>()); return make_tuple(sum_k_smallest, sum_k_largest, product_k_smallest, product_k_largest);}// Driver codeint main(){ vector<int> arr = { 4, 2, 12, 13, 5, 19 }; int k = 3; auto result = sum_and_product_of_k_primes(arr, k); cout << "Sum of the k smallest primes: " << get<0>(result) << endl; cout << "Sum of the k largest primes: " << get<1>(result) << endl; cout << "Product of the k smallest primes: " << get<2>(result) << endl; cout << "Product of the k largest primes: " << get<3>(result) << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set;public class PrimeOperations { public static boolean isPrime(int n) { // Function to check if a number is prime if (n < 2) { return false; } for (int i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } public static List<Integer> sumAndProductOfKPrimes(List<Integer> arr, int k) { // Function to calculate the sum and product of the k smallest and k largest primes Set<Integer> primes = new HashSet<>(); for (int p : arr) { // Check if each element in the array is a prime and add to the set if (isPrime(p)) { primes.add(p); } } // Convert the set of primes to a list and sort it List<Integer> sortedPrimes = new ArrayList<>(primes); sortedPrimes.sort(null); // Get the k smallest and k largest primes from the sorted list List<Integer> kSmallestPrimes = sortedPrimes.subList(0, k); List<Integer> kLargestPrimes = sortedPrimes.subList(sortedPrimes.size() - k, sortedPrimes.size()); // Calculate the sum of k smallest primes and k largest primes int sumKSmallest = 0; int sumKLargest = 0; for (int prime : kSmallestPrimes) { sumKSmallest += prime; } for (int prime : kLargestPrimes) { sumKLargest += prime; } // Calculate the product of k smallest primes and k largest primes int productKSmallest = 1; int productKLargest = 1; for (int prime : kSmallestPrimes) { productKSmallest *= prime; } for (int prime : kLargestPrimes) { productKLargest *= prime; } List<Integer> result = new ArrayList<>(); result.add(sumKSmallest); result.add(sumKLargest); result.add(productKSmallest); result.add(productKLargest); return result; } public static void main(String[] args) { List<Integer> arr = List.of(4, 2, 12, 13, 5, 19); int k = 3; List<Integer> result = sumAndProductOfKPrimes(arr, k); // Print the results System.out.println("Sum of the k smallest primes: " + result.get(0)); System.out.println("Sum of the k largest primes: " + result.get(1)); System.out.println("Product of the k smallest primes: " + result.get(2)); System.out.println("Product of the k largest primes: " + result.get(3)); }}// This code is contributed by shivamgupta310570 |
Python3
import mathdef is_prime(n): # Function to check if a number is prime if n < 2: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return Truedef sum_and_product_of_k_primes(arr, k): # Function to calculate the sum and product of the k smallest and k largest primes primes = set() for p in arr: # Check if each element in the array is a prime and add to the set if is_prime(p): primes.add(p) # Convert the set of primes to a list and sort it sorted_primes = sorted(primes) # Get the k smallest and k largest primes from the sorted list k_smallest_primes = sorted_primes[:k] k_largest_primes = sorted_primes[-k:] # Calculate the sum of k smallest primes and k largest primes sum_k_smallest = sum(k_smallest_primes) sum_k_largest = sum(k_largest_primes) # Calculate the product of k smallest primes and k largest primes product_k_smallest = 1 for prime in k_smallest_primes: product_k_smallest *= prime product_k_largest = 1 for prime in k_largest_primes: product_k_largest *= prime return [sum_k_smallest, sum_k_largest, product_k_smallest, product_k_largest]# Driver codearr = [4, 2, 12, 13, 5, 19]k = 3result = sum_and_product_of_k_primes(arr, k)# Print the resultsprint("Sum of the k smallest primes:", result[0])print("Sum of the k largest primes:", result[1])print("Product of the k smallest primes:", result[2])print("Product of the k largest primes:", result[3]) |
C#
using System;using System.Collections.Generic;using System.Linq;class GFG{ // This function checks if a given number is prime static bool IsPrime(int n) { if (n < 2) return false; // Checking if 'n' has a factor in the range [2, n ^ 0.5] for (int i = 2; i <= Math.Sqrt(n); i++) if (n % i == 0) { return false; } return true; } // This function returns a tuple containing the sum and product of the k smallest and larger prime numbers static (int, int, int, int) SumAndProductOfKPrimes(List<int> arr, int k) { Dictionary<int, bool> primes = new Dictionary<int, bool>(); // Marking prime values foreach (int p in arr) if (IsPrime(p)) primes[p] = true; // Storing a list of sorted prime values List<int> sortedPrimes = primes.Keys.ToList(); sortedPrimes.Sort(); // Extracting the k smallest prime values List<int> kSmallestPrimes = sortedPrimes.Take(k).ToList(); sortedPrimes.Sort((a, b) => b.CompareTo(a)); // Extracting the k largest prime values List<int> kLargestPrimes = sortedPrimes.Take(k).ToList(); // Calculating the sums of the k smallest and largest prime values int sumKSmallest = kSmallestPrimes.Sum(); int sumKLargest = kLargestPrimes.Sum(); // Calculating the products of the k smallest and largest prime values int productKSmallest = kSmallestPrimes.Aggregate(1, (x, y) => x * y); int productKLargest = kLargestPrimes.Aggregate(1, (x, y) => x * y); return (sumKSmallest, sumKLargest, productKSmallest, productKLargest); } // Driver code static void Main() { List<int> arr = new List<int> { 4, 2, 12, 13, 5, 19 }; int k = 3; // Function call var result = SumAndProductOfKPrimes(arr, k); Console.WriteLine("Sum of the k smallest primes: " + result.Item1); Console.WriteLine("Sum of the k largest primes: " + result.Item2); Console.WriteLine("Product of the k smallest primes: " + result.Item3); Console.WriteLine("Product of the k largest primes: " + result.Item4); }}// by phasing17 |
Javascript
function is_prime(n) { // Function to check if a number is prime if (n < 2) { return false; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return false; } } return true;}function sum_and_product_of_k_primes(arr, k) { // Function to calculate the sum and product of the k smallest and k largest primes const primes = new Set(); for (let p of arr) { // Check if each element in the array is a prime and add to the set if (is_prime(p)) { primes.add(p); } } // Convert the set of primes to an array and sort it const sorted_primes = [...primes].sort((a, b) => a - b); // Get the k smallest and k largest primes from the sorted array const k_smallest_primes = sorted_primes.slice(0, k); const k_largest_primes = sorted_primes.slice(-k); // Calculate the sum of k smallest primes and k largest primes const sum_k_smallest = k_smallest_primes.reduce((acc, curr) => acc + curr, 0); const sum_k_largest = k_largest_primes.reduce((acc, curr) => acc + curr, 0); // Calculate the product of k smallest primes and k largest primes const product_k_smallest = k_smallest_primes.reduce((acc, curr) => acc * curr, 1); const product_k_largest = k_largest_primes.reduce((acc, curr) => acc * curr, 1); return [sum_k_smallest, sum_k_largest, product_k_smallest, product_k_largest];}// Driver codeconst arr = [4, 2, 12, 13, 5, 19];const k = 3;const result = sum_and_product_of_k_primes(arr, k);// Print the resultsconsole.log("Sum of the k smallest primes:", result[0]);console.log("Sum of the k largest primes:", result[1]);console.log("Product of the k smallest primes:", result[2]);console.log("Product of the k largest primes:", result[3]); |
Output:
Sum of the k smallest primes: 20
Sum of the k largest primes: 37
Product of the k smallest primes: 130
Product of the k largest primes: 1235
Time Complexity: O(nlogn) (sorting) + O(nsqrt(m)*logk) (finding primes and extracting k smallest/largest primes), where m is the maximum value in the input array.
Auxiliary Space: O(n)
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!
