Data Modelling & AI Data Structure & Algorithm

Sum and product of k smallest and k largest prime numbers in the array

23 June 2025

0

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 array
void 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 code
int 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 heapq
 
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 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 = 3
primeSumAndProduct(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 array
 
using 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).length
let k = 3
primeSumAndProduct(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 code
int 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 math
 
def 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 True
 
def 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 code
arr = [4, 2, 12, 13, 5, 19]
k = 3
result = sum_and_product_of_k_primes(arr, k)
 
# Print the results
print("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 code
const arr = [4, 2, 12, 13, 5, 19];
const k = 3;
const result = sum_and_product_of_k_primes(arr, k);
 
// Print the results
console.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!

Sum and product of k smallest and k largest prime numbers in the array

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

The best Android browser you have never heard of

Quick Share/AirDrop gets Qualcomm backing, leaving old Pixels out in the cold, but for how long?

Samsung Galaxy S26 may debut a Perplexity-powered Bixby

Google’s 15 year old Pixel concept. [Video]

EDITOR PICKS

The best Android browser you have never heard of

Quick Share/AirDrop gets Qualcomm backing, leaving old Pixels out in the cold, but for how long?

Samsung Galaxy S26 may debut a Perplexity-powered Bixby

POPULAR POSTS

The best Android browser you have never heard of

Quick Share/AirDrop gets Qualcomm backing, leaving old Pixels out in the cold, but for how long?

Samsung Galaxy S26 may debut a Perplexity-powered Bixby

POPULAR CATEGORY

ABOUT US

FOLLOW US