Sum of all elements between k1’th and k2’th Smallest Elements

In this tutorial, we will look at how to determine sum of all given elements between two given indexes’ smallest elements. Assuming an array of integers and two numbers, k1 and k2, calculate the sum of all entries in the array between the smallest k1 and k2 elements. It's safe to assume that (1 = k1 k2 = n) and all array items are unique.

Method No. 1 (Sorting)

We will sort the given array using an O(n log n) sorting algorithm, such as Merge Sort or Heap Sort, and then return the sum of all entries in the sorted array between indexes k1 and k2.

The following is how the aforementioned concept was put into action:

C++ Program:

// CPP to determine the sum of all elements in a given array between the K1'th and K2'th smallest elements.
#include <bits/stdc++.h> 
using namespace std; 
int sum_between_two_Kth ( int array [], int num, int k1, int k2 ) 
{ 
    // Sorting the given array
    sort ( array, array + num ); 


    return accumulate ( array + k1, array + k2 - 1, 0 ); 
} 
// Driver Code
int main () 
{ 
    int array [] = { 21, 9, 23, 5, 13, 11, 15 }; 
    int k1 = 3, k2 = 6; 
    int num = sizeof ( array ) / sizeof ( array [0] ); 
    cout << sum_between_two_Kth ( array, num, k1, k2 ); 
    return 0; 
}

Output:

28

Time Complexity: O(n log n)

Method No. 2 (Using Min Heap)

Using a min heap, we can improve the above approach.

1) Create a heap from all array elements. (This operation takes O(n) time.)

2) Perform at least k1 extractions. (It takes O(K1 Log n) seconds to complete this phase.)

3) Extract k2 - k1 - 1 times and combine all extracted parts. (This phase takes O ((K2 - k1) * Log n) time to complete.)

C++Program:

#include <bits/stdc++.h> 
using namespace std; 
  
int num = 7; 
void minheapify ( int array [], int index ) 
{ 
    int s = index; 
    int l = 2 * index + 1; 
    int r = 2 * index + 2; 
  
    if ( l < num && array [ l ] < array [ s ] ) 
        s = l; 
  
    if ( r < num && array [ r ] < array [ s ] ) 
        s = r; 
  
    if ( s != index ) { 
        swap ( array [s], array [index] ); 
        minheapify ( array, s ) ; 
    } 
} 
int main () 
{ 
    int i = 0; 
    int k1 = 3; 
    int k2 = 6; 
    int array [] = { 21, 9, 23, 5, 13, 11, 15 }; 
    int answer = 0; 
    for ( i = ( num / 2) - 1; i >= 0; i-- ) { 
        minheapify ( array, i ); 
    } 
    k1--; 
    k2--; 
    for ( i = 0; i <= k1; i++ ) { 
        array [0] = array [ num - 1]; 
        num--; 
        minheapify ( array, 0 ); 
    }
    for ( i = k1 + 1; i < k2; i++ ) { 
        answer += array [0]; 
        array [0] = array [ num - 1 ]; 
        num--; 
        minheapify ( array, 0) ; 
    } 
    cout << answer; 
    return 0; 
}

Output:

28

This method's overall time complexity is O(n + k2 Log n), which is faster than the sorting-based method.