Header Ads Widget

Maximize the sum | Hackerearth practice problem solution

Rajnish Tripathi 20:06

   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

1≤T≤10001≤K≤N≤5×105−109≤Ai≤109Sum 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:-
Tags:

Post a Comment

0 Comments