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

$$\begin{gathered} 1\le T\le 1000 \\ 1\le K\le N\le 5\times {10}^5 \\ -{10}^9\le A_i\le {10}^9 \\ \text{Sum of N over all test cases does not exceed }2\times {10}^6 \end{gathered}$$

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:-

• Hackerearth Problems:-
  
  
  • Very Cool numbers | Hacker earth solution
  • Vowel Recognition | Hackerearth practice problem solution
    
  • Birthday party | Hacker earth solution
  • Most frequent | hacker earth problem solution
  • program to find symetric difference of two sets
  •  cost of balloons | Hacker earth problem solution
  • Chacha o chacha | hacker earth problem solution
  • jadu and dna | hacker earth solution
  • Bricks game | hacker earth problem
  • Anti-Palindrome strings | hacker earth solution
  • connected components in the graph | hacker earth data structure
  • odd one out || hacker earth problem solution
  • Minimum addition | Hackerearth Practice problem
    
  • The magical mountain | Hackerearth Practice problem
    
  • The first overtake | Hackerearth Practice problem
    
  Hackerrank Problems:-
  •  Playing With Characters | Hackerrank practice problem solution
  • Sum and Difference of Two Numbers | hackerrank practice problem solution
    
  • Functions in C | hackerrank practice problem solution
    
  • Pointers in C | hackerrank practice problem solution
    
  • Conditional Statements in C | Hackerrank practice problem solution
    
  • For Loop in C | hackerrank practice problem solution
  Data structure:-
  
  •   Program to find cycle in the graph
  • Implementation of singly link list
  • Implementation of queue by using link list
  • Algorithm of quick sort
  • stack by using link list
  • program to find preorder post order and inorder of the binary search tree
  • Minimum weight of spanning tree
    
  • Preorder, inorder and post order traversal of the tree
    
  Key points:-
  • How to set limit in the floating value in python
    
  • What is boolean data type
  • How to print any character without using format specifier

  
  

  Must check this:-
  

  • PPS lab all the problems of 1st year 
  • C- program of CPU scheduling Algorithms

         MCQs:-

• Engineering mathematics -4 MCQs
• CSS (Computer cyber security ) MCQS