Maximum possible Sum of the Array After Performing the Given Operations

Vaibhav Agarwal
Last Updated: Jun 30, 2022
Difficulty Level :
MEDIUM

Introduction

Arrays are one of the simplest and most common Data Structures. They are involved in many problems which are asked in competitive coding contests as well as interviews. Here in this problem, we are going to take a look at one such problem and discuss its possible solutions.

Problem Statement

The problem states that we are given an array arr[] of size n and two more arrays x[] and y[] of size P each. For each of the array x[] and y[], we can perform the following:

  • We can select at most x[i] elements from the arr[], and can replace selected elements with y[i], for each query from x[] and y[]. 
  • After performing all the P operations, the maximum possible sum of the array. 
     

We will discuss the brute and optimized approach and the sample test cases and c++ code. 

Sample Examples

Example 1:

Input : arr[] = {2,6,3,8,5,5,10,9,7,4}, P = 3, 
x[] =  {1,4,2}
y[] = {10,3,4}

Output: Maximum possible sum is 68

Explanation: 
For i = 1, we can replace a maximum of 1 element from arr[] with integer 10. 9 elements of arr[] are smaller than 10, so we will replace the smallest element, i.e., 2. 
After Completing operation arr[] becomes {10,6,3,8,5,5,10,9,7,4}.
For i = 2, we can replace a maximum of 4 elements from arr[] with integer 3. 0 elements of arr[] are smaller than 3, so we will replace nothing. 
After completing operation arr[] becomes {10,6,3,8,5,5,10,9,7,4}.
For i = 3, we can replace a maximum of 2 elements from arr[] with integer 4. 1 element of arr[] are smaller than 4, so we will replace the smaller element. 
After completing operation arr[] becomes {10,6,4,8,5,5,10,9,7,4}.

 

Example 2:

Input: arr[] = {100,200,300,200}, P = 2 
          x[] = {3,2}
          y[] = {90,100}
          
Output: Maximum possible sum is 800

Explanation:
For i = 1, we can replace a maximum of 3 elements from arr[] with integer 90. 0 elements of arr[] are smaller than 90, so we will replace nothing. 
For i = 2, we can replace a maximum of 2 elements from arr[] with integer 100. 0 elements of arr[] are smaller than 100, and we will replace nothing. 

Brute Force Approach

In the brute force approach, we will pick up all the elements that are lesser than y[i] for each i, and will replace the first smallest x[i] number of elements from the picked-up elements with y[i].  

Algorithm

  1. We will use two nested for loops, the outer loop will iterate over the x array and the inner loop will find the elements that are smaller than y[i] for each i. 
  2. We will declare a vector pair to store the elements that are smaller than y[i] for i.
  3. We will sort the vector, and replace the first x[i] number of elements of the vector in array arr[]. 
  4. Finally, find the sum for the whole array using the sum variable.  

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
void MaxSumPossible(int *arr, int n,int q,int *x,int *y){
    // iterating over the array x and y
    for(int i=0;i<q;i++){
        // creating vector for storing the
        // element less than y[i]
        // and storing its index
        vector<pair<int,int>>v;
        
        for(int j=0;j<n;j++){
            // if element is less than y[i]
            // push element and its index into the vector
            if(arr[j]<y[i]){
                v.push_back({arr[j],j});
            }
        }
        
        // sorting the vector
        sort(v.begin(),v.end());
        
        // replacing the first smallest x[i] number of element
        // with y[i]
        for(int j=0;j<x[i] && j<v.size();j++){
            arr[v[j].second] = y[i];
        }
    }
    // declaring sum variable for finding the total sum
    int sum = 0;
    
    // iterating over the array to find the sum
    for(int i=0;i<n;i++){
        sum += arr[i];
    }
    // printing the final sum
    cout << "Maximum possible sum is " << sum << "\n";
}
int main()
{
    int ar[] = {2,6,3,8,5,5,10,9,7,4};
    int n = (sizeof ar) / (sizeof ar[0]);
    int q = 3;
    int x[] =  {1,4,2};
    int y[] = {10,3,4};
    MaxSumPossible(ar, n, q, x, y);

    return 0;
}

 

Output:

Maximum possible sum is 68

Complexity Analysis

Time Complexity: O(N^2)

Explanation: Since we are using two nested for loops, time complexity will be N^2.

Space ComplexityO(N)

Explanation: We are using vectors to store the elements that are smaller than y[i] for each i, and in the worst case every element of array arr[] can be smaller than y[i], so space complexity is O(N). 

Optimized Approach(Max heap)

This problem can be solved using the Priority Queue (Max heap). The idea is simple we will push all the elements of arr[] and y[], with their frequency. We will then take the first n elements of the max heap to add to our sum. It will be the maximum sum possible as we take the n maximum possible value of the array. 

(Also, see Heap and Priority Queue)

Algorithm

  1. Make a priority queue of pairs to store the element along with frequency.
  2. Now push all the elements of arr[] and initially assume that the frequency of each element in arr[i] is 1. 
  3. Now push all the elements of Y[], along with frequency x[] as a pair of {y[i], x[i]}.
  4. Finally, add the top n elements from the priority queue by running a loop. 
illustration max heap


Implementation in C++

// C++ implementation for
// Maximum possible Sum of the Array
//After performing the given operations
#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum sum possible after performing P number of queries.
void MaxSumPossible(int arr[], int n, int P, int x[], int y[])
{
    // maxSum to store the maximumSumPossible
    int maxSum = 0;
    // priority queue to
    // get maximum sum
    priority_queue<pair<int, int> > pq;

    // push the arr[i], and assume
    // frequency to be 1 for each element.
    for (int i = 0; i < n; i++)
        pq.push({ arr[i], 1 });

    // push pair as y[i] (element to be replace with),
    // x[i](number of elements to be replaced)
    for (int i = 0; i < P; i++)
        pq.push({ y[i], x[i] });

    // add the first largest n elements
    while (n > 0) {

        pair<int,int>currTop;
        // currTop is the current largest element in priority queue
        currTop = pq.top();

        // pop from the priority queue
        pq.pop();
        maxSum += currTop.first * min(n, currTop.second);

        // Update n
        n -= currTop.second;
    }
    // printing the maximum possible sum
    cout << "Maximum possible sum is " << maxSum << "\n";
}
// Driver code
int main()
{
    int ar[] = {100,200,300,200};
    int n = (sizeof ar) / (sizeof ar[0]);
    int q = 2;
    int x[] = {3,2 };
    int y[] = {90,100 };
    MaxSumPossible(ar, n, q, x, y);

    return 0;
}

 

Output: 

Maximum possible sum is 800

Complexity Analysis

Time Complexity: O(NlogN)

Explanation: N is the total number of elements inserted in the priority queue, i.e., N = (n + P). 

Where n is the number of elements in the arr[], and P is the number of elements in the x[] or y[]. We are inserting the maximum of N elements, and each element takes logN time to get inserted; therefore, TC is O(NlogN).

Space ComplexityO(N)

Explanation: We are inserting N elements in priority_queue. Therefore it will take the O(N) space. 

Frequently Asked Questions

Priority_queue in C++ STL is minheap or maxheap and what is its syntax? 

Priority_queue in C++ STL is maxheap, and syntax for writing priority_queue is “priority_queue<type>name”. 

What is the time complexity for insertion, deletion, updating, and searching in priority_queue? 

Every operation in priority_queue takes logN time, where N is the number of elements. 

What are the maximum elements in a heap with height h? 

It will be 2h-1, while the minimum number of elements in a heap with the same height will be 2h-1+1 (One more than nodes with height h-1)

Conclusion

In this article, we discussed the problem of finding the maximum possible sum after performing the given operations. We discussed the two approaches, i.e., brute force and optimized approach using the max heap. We hope you understand the problem and solution properly. Now you can do more similar questions. 

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on  CodeStudio.

Until then, Keep Learning and Keep Coding.

Was this article helpful ?
0 upvotes