Statement - Given an array of positive integers and two positive integers K1 and K2. Find sum of all elements greater tha K1th and smaller than K2th smallest elements of array.
Example 1:
Input:
7
20 8 22 4 12 10 14
3 6
Output:
26
Explanation:
3rd smallest element is 10
6th smallest element is 20
Sum of all element between
K1 & K2 is 12 + 14 = 26
Problem Link - Click
Code - Time Complexity O(nlogn), Space Complexity O(n).
void k1_smallest(long long a[], long long n, long long k1, long long &m)
{
set<long long> pq;
for(long long i = 0; i < n; i++)
{
pq.insert(a[i]);
if((int)pq.size() > (int) k1)
{
auto h = pq.end();
h--;
pq.erase(h);
}
}
auto h = pq.end();
h--;
if((int) pq.size() < k1)
m = 1e18;
else
m = *h;
}
long long sumBetweenTwoKth(long long a[], long long n, long long k1, long long k2)
{
// Your code goes here
long long m1, m2;
k1_smallest(a, n, k1, m1);
if(k2 <= n)
k1_smallest(a, n, k2, m2);
else
m2 = 1e18;
if(m1 > m2)
swap(m1, m2);
long long ans = 0;
for(long long i = 0; i < n; i++)
{
if(a[i] > m1 && a[i] < m2)
ans += a[i];
}
return ans;
}
0 Comments