Maximize the sum | Hackerearth practice problem solution

   Problem:-

You are given an array 

A

 of 

N

 integers. You want to choose some integers from the array subject to the condition that the number of distinct integers chosen should not exceed 

K

. Your task is to maximize the sum of chosen numbers. 

You are given 

T

 test cases.

Input format

  • The first line contains a single integer 
    T

     denoting the number of test cases.

  • The first line of each test case contains two space-separated integers 
    N

     and 

    K

     denoting the length of the array and the maximum number of distinct integers you can choose.

  • The second line of each test case contains 
    N

     space-separated integers denoting the integer array 

    A

    .

Output format

For each test case(in a separate line), print the maximum sum you can obtain by choosing some elements such that the number of distinct integers chosen is at most 

K

. If you cannot choose any element, output 

0

.

Constraints

1T10001KN5×105109Ai109Sum of N over all test cases does not exceed 2×106

Sample Input
2
4 1
3 -1 2 5
4 2
2 1 2 5
Sample Output
5
9
Time Limit: 1.5
Memory Limit: 256
Source Limit:
Explanation

In the first test case, we have 

N=4,K=1

A=[3,1,2,5]

. Since we can choose atmost 1 distinct integer, we choose 

5

. The sum is also 

5

 and we output it.

In the second test case, we have 

N=4,K=2

A=[2,1,2,5]

. We need to choose atmost 2 distinct integers, we choose 

2,2,5

. Note that the condition is choosing atmost 

K

 distinct integers. So we can choose repeated number as many times as we want. The sum is 

2+2+5=9

 and we output it.

10

Code:-

 This solution is based on the c++ language and you can submit it c++14 and c++17 also.
In this solution first three lines of the main function is only for the decreasing the time of execution of the program..
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

This is your choice that you want to use this or not but in some cases the code may take more time in execution and that time we need it .

#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define nline “n”
#define f first
#define s second
#define um unordered_map
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
um<ll,ll>m;
for (int i = 0; i < n; i++)
{
ll a;
cin>>a;
m[a] += a;
}
vector<ll>v;
for(auto &val:m){
v.pb(val.s);
}
sort(v.begin(), v.end(),greater<ll>());
ll sum = 0;
for (int i = 0; i < k; i++)
{
if(sum+v[i] > sum) sum += v[i];
}
cout<<sum<<nline;
}

return 0;
}

Recommended Post:-

         MCQs:-

Leave a Reply

Your email address will not be published.