Heap: Sum of all the elements between k1 and k2 smallest elements

Problem Statement:

You are given array of integers and 2 numbers k1 and k2.
You need to find the sum of all the elements between the given 2 k1 and k2 elements in the array.

Example

Input : arr[] = {20, 8, 22, 4, 12, 10, 14}, k1 = 3, k2 = 6
Output : 26
Here 3rd smallest element is 10.
And 6th smallest element is 20.
Sum of all element between k1 & k2 is 12 + 14 = 26

Solution

We can solve this problem by using Min Heap.

Create a min heap of all the elements.

Extract all min elements k1 times.

Extract minimum k2 – k1 -1 and then sum all the extracted elements.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 

using namespace std;


 
int sum_between_k1_k2_sortest(int arr[], int n, int k1, int k2)
{
    priority_queue<int,vector<int>,greater<int>> min_heap;
    int sum = 0;
    int count = 0;

    /* Insert all elements to max heap */
    for( int i = 0 ; i < n ; i++ )
    {
        min_heap.push(arr[i]);
    }

    /* Remove first k1 elements */
    count = k1;
    while(count--)
    {
        min_heap.pop();
    }

    count = k2-k1;

    /* Now store sun of these req elements */
    while(count-- > 1)
    {
        sum+=min_heap.top();
        min_heap.pop();
    }

    return sum;
}
 
int main()
{
    int arr[] = { 20, 8, 22, 4, 12, 10, 14 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int k1 = 3;
    int k2 = 6;
    cout << "Sum is " << sum_between_k1_k2_sortest(arr, size, k1, k2 )<<endl;
    return 0;
}

Output:

Sum is 26