Find Minimum Sum of price required to select atleast M distinct values from array else return -1

We will be given two arrays having n elements from which one array values [] will be the collection of values and another array price[] will be the collection of prices. We have to select the m distinct values such that the sum of the price will be minimum.

Example

Let's understand with help of an example as explained below: -

Input 1

n = 8, m = 3

values [] \= { 1, 3, 2, 2, 4, 1, 3, 5 }

price [] \= { 3, 3, 0, 1, 2, 4, 1, 4}

Output

Minimum Rupees required = 3

Explanation

First, we have checked whether there are at least m distinct categories of elements available in values [] or not. After checking we got there are 5 distinct values in values [] as you can see which is greater than m as shown in the above example and then we gave searched the minimum price required to select 3 distinct values among the 5 values available in the values [].

So, we got that array of minimum prices of distinct values of values [] \= { 0, 1, 2, 3, 4}

And we wanted the minimum price for only distinct values of values []. So, add the first 3 smallest prices i.e 0+1+2 = 3.

Efficient Algorithm to solve the above Problem

Step 1: First, we will be checking the distinct elements of values [] are greater than m or not.

Step 2: If values of distinct elements in values [] are less than m then return -1.

Step 3: If available distinct values are greater than m then we will be storing the minimum price among the similar elements of values [] into the vector and so on.

Step 4: After storing the minimum price of all the distinct values [] sort them in ascending order.

Step 5: And then iterate the sorted vector up to m and store the sum into a variable name ans up to the k iteration.

Step 6: Print the sum that has been stored into ans.

Implementation for the above approach is given below: -

#include<bits/stdc++.h>
using namespace std;

// function for finding the minimum price
long long minimumSum(int n, int m, vector<int> values, vector<int> price){
    long long ans = 0;

      // intialize the map for counting the
      // number of distinct elements of values[]
      // array
    map<int, int> count;
    for(int i = 0; i < n; count[values[i]]++, i++);

      // checking the size of map 
      // that greater than 
      // m distinct elements or not
      if(count.size() < m){
        ans = -1;
    }

      // if size of map is greater than or equal to
      // m elements
    else{
        count.clear();
        set<int> track;

          // intializing the sortTime array 
          // to store the minimum price the among
          // the similar values of values[] array
        vector<int> sortTime; 
        for(int i = 0; i < n; i++){
            if(track.find(values[i]) != track.end()){
                count[values[i]] = min(count[values[i]], price[i]);
            }
            else{
                track.insert(values[i]);
                count[values[i]] = price[i];
            }
        }


        for(auto value: count){
            sortTime.push_back(value.second);
        }

          // sorting the price in ascending order
        sort(sortTime.begin(), sortTime.end());
        for(int i = 0; i < m; i++){
            ans += (sortTime[i]*1LL);
        }
    }

      // returning the final answer
    return ans;
}


// function for printing the final answer
void printAns(long long ans){
    cout << ans;
    cout << endl;
}

// Driver code
int main() {
      // Input 1
    int n1 = 8, m1 = 3;
    vector<int> values1 = {1, 3, 2, 2, 4, 1, 3, 5};
    vector<int> price1 =   {3, 3, 0, 1, 2, 4, 1, 4};
    long long ans1 = minimumSum(n1, m1, values1, price1);
    printAns(ans1);

    // Input 2
    int n2 = 5, m2 = 3;
    vector<int> values2 = {1, 1, 2, 2, 1};
    vector<int> price2 =   {1, 1, 0, 3, 5};
    long long ans2 = minimumSum(n2, m2, values2, price2);
    printAns(ans2);

    return 0;
}

Output

3

-1

Time complexity: O(n\logn)*

Auxiliary Space: O(n)