Given array arr[] of positive integers, an integer Q, and arrays X[] and Y[] of size Q. For each element in arrays X[] and Y[], we can perform the below operations:
- For each query from array X[] and Y[], select at most X[i] elements from array arr[] and replace all the selected elements with integer Y[i].
- After performing Q operations, the task is to obtain maximum sum from the array arr[].
Examples:
Input: arr[] = {5, 2, 6, 3, 8, 5, 4, 7, 9, 10}, Q = 3, X[] = {2, 4, 1}, Y[] = {4, 3, 10}
Output: 68
Explanation:
For i = 1,
We can replace atmost 2 elements from array arr[] with integer 4. Here 2 element of array arr[] are smaller than 4 so we will replace elements 2 and 3 from array arr[] with 4 and arr[] becomes {5, 4, 6, 4, 8, 5, 4, 7, 9, 10}.
For i = 2,
We can replace at most 4 elements from array ar[] with integer 3, but no element of array arr[] is smaller than 3. So we will not replace anything.
For i = 3,
We can replace at most 1 element from array arr[] with integer 10, 9 elements of array arr[] are smaller than 10. To get the maximum sum, we will replace the smallest element from array arr[] with 10. Array arr[] after 3rd operation = {5, 10, 6, 4, 8, 5, 10, 7, 9, 10 }. The maximum possible sum is 68.
Input: ar[] = {200, 100, 200, 300}, Q = 2, X[] = {2, 3}, Y[] = {100, 90}
Output: 800
Explanation:
For i = 1,
We can replace atmost 2 elements from array arr[] with integer 100, no element of array arr[] is smaller than 100. So we will replace 0 elements.
For i = 2,
We can replace at most 3 elements from array arr[] with integer 90, no element of array arr[] is smaller than 90. So we will replace 0 elements. So the maximum sum we can obtain after q operation is 800.
Naive Approach: The naive idea is to pick X[i] number elements from the array arr[]. If the elements in the array are less than Y[i] then update X[i] of such elements.
Time Complexity: (N2), as we will be using nested loops for traversing N*N times. Where N is the number of elements in the array.
Auxiliary Space: O(1), as we will not be using any extra space.
Efficient Approach: The idea is to use a priority queue to get the element with higher value before the element with lower value, precisely priority queue of pairs to store value with its frequency. Below are the steps:
- Insert each element of the array arr[] with their occurrence in the priority queue.
- For each element(say X[i]) in the array X[] do the following:
- Choose at most X[i] number of minimum element from the priority queue.
- Replace it with Y[i] if choose element is less than Y[i].
- Insert back the replaced element into the priority queue with their corresponding frequency.
- After the above operations the array arr[] will have elements such that sum of all element is maximum. Print the sum.
Below is the implementation of the above approach:
C++
// C++ implementation to find the// maximum possible sum of array// after performing given operations#include <bits/stdc++.h>using namespace std;// Function to get maximum// sum after q operationsvoid max_sum(int ar[], int n, int q, int x[], int y[]){ int ans = 0, i; // priority queue to // get maximum sum priority_queue<pair<int, int> > pq; // Push pair, value and 1 // in the priority queue for (i = 0; i < n; i++) pq.push({ ar[i], 1 }); // Push pair, value (to be replaced) // and number of elements (to be replaced) for (i = 0; i < q; i++) pq.push({ y[i], x[i] }); // Add top n elements from // the priority queue // to get max sum while (n > 0) { // pr is the pair // pr.first is the value and // pr.second is the occurrence auto pr = pq.top(); // pop from the priority queue pq.pop(); // Add value to answer ans += pr.first * min(n, pr.second); // Update n n -= pr.second; } cout << ans << "\n";}// Driver codeint main(){ int ar[] = { 200, 100, 200, 300 }; int n = (sizeof ar) / (sizeof ar[0]); int q = 2; int x[] = { 2, 3 }; int y[] = { 100, 90 }; max_sum(ar, n, q, x, y); return 0;} |
Java
// Java implementation to find the // maximum possible sum of array // after performing given operations import java.util.*;import java.lang.*;class GFG{static class pair{ int first, second; pair(int first, int second) { this.first = first; this.second = second; }}// Function to get maximum // sum after q operations static void max_sum(int ar[], int n, int q, int x[], int y[]) { int ans = 0, i; // priority queue to // get maximum sum PriorityQueue<pair> pq = new PriorityQueue<>( (a, b) -> Integer.compare(a.second, b.second)); // Push pair, value and 1 // in the priority queue for(i = 0; i < n; i++) pq.add(new pair(ar[i], 1 )); // Push pair, value (to be replaced) // and number of elements (to be replaced) for(i = 0; i < q; i++) pq.add(new pair(y[i], x[i])); // Add top n elements from // the priority queue // to get max sum while (n > 0) { // pr is the pair // pr.first is the value and // pr.second is the occurrence pair pr = pq.peek(); // pop from the priority queue pq.poll(); // Add value to answer ans += pr.first * Math.min(n, pr.second); // Update n n -= pr.second; } System.out.println(ans); } // Driver Codepublic static void main (String[] args){ int ar[] = { 200, 100, 200, 300 }; int n = ar.length; int q = 2; int x[] = { 2, 3 }; int y[] = { 100, 90 }; max_sum(ar, n, q, x, y); }}// This code is contributed by offbeat |
Python3
# Python implementation to find the# maximum possible sum of array# after performing given operationsfrom queue import PriorityQueuedef max_sum(arr, n, q, x, y): ans = 0 i = 0 # priority queue to # get maximum sum pq = PriorityQueue() # Push pair, value and 1 # in the priority queue for i in range(n): pq.put((-arr[i], 1)) # Push pair, value (to be replaced) # and number of elements (to be replaced) for i in range(q): pq.put((-y[i], x[i])) # Add top n elements from # the priority queue # to get max sum while n > 0: # pr is the pair # pr.first is the value and # pr.second is the occurrence pr = pq.get() # Add value to answer ans += abs(pr[0]) * min(n, pr[1]) # Update n n -= pr[1] print(ans)ar = [200, 100, 200, 300]n = len(ar)q = 2x = [2, 3]y = [100, 90]max_sum(ar, n, q, x, y)# This code is provided by sdeadityasharma |
C#
// C# implementation to find the// maximum possible sum of array// after performing given operationsusing System;using System.Linq;using System.Collections.Generic;public class Pair { public int first; public int second; public Pair(int first, int second) { this.first = first; this.second = second; }}public class GFG { // Function to get maximum // sum after q operations static void MaxSum(int[] ar, int n, int q, int[] x, int[] y) { int ans = 0; int i, j; // Push pair, value and 1 // in the array List<Pair> pq = new List<Pair>(); for (i = 0; i < n; i++) pq.Add(new Pair(ar[i], 1)); // Push pair, value (to be replaced) // and number of elements (to be replaced) for (i = 0; i < q; i++) pq.Add(new Pair(y[i], x[i])); pq = pq.OrderBy(p => p.second).ToList(); // Add top n elements from // the priority queue // to get max sum while (n > 0) { // pr is the pair // pr.first is the value and // pr.second is the occurrence var pr = pq[0]; // pop from the priority queue pq.RemoveAt(0); // Add value to answer ans += pr.first * Math.Min(n, pr.second); // Update n n -= pr.second; } Console.WriteLine(ans); } // Driver Code public static void Main(string[] args) { int[] ar = { 200, 100, 200, 300 }; int n = ar.Length; int q = 2; int[] x = { 2, 3 }; int[] y = { 100, 90 }; MaxSum(ar, n, q, x, y); }}// This code is contributed by phasing17 |
Javascript
// Javascript implementation to find the// maximum possible sum of array// after performing given operations// Function to get maximum// sum after q operations function max_sum(arr, n, q, x, y) { let ans = 0; // priority queue to // get maximum sum let pq = []; // Push pair, value and 1 // in the priority queue for (let i = 0; i < n; i++) { pq.push([-arr[i], 1]); } // Push pair, value (to be replaced) // and number of elements (to be replaced) for (let i = 0; i < q; i++) { pq.push([-y[i], x[i]]); } pq.sort((a, b) => a[0] - b[0]); // Add top n elements from // the priority queue // to get max sum while (n > 0) { // pr is the pair // pr.first is the value and // pr.second is the occurrence let pr = pq.shift(); // Add value to answer ans += Math.abs(pr[0]) * Math.min(n, pr[1]); // Update n n -= pr[1]; } console.log(ans); } // Driver code let ar = [200, 100, 200, 300]; let n = ar.length; let q = 2; let x = [2, 3]; let y = [100, 90]; max_sum(ar, n, q, x, y); // This code is contributed by Aman Kumar. |
800
Time Complexity: O(N*log2N), as we are using a loop to traverse N times and priority queue operation will take log2N times. Where N is the number of elements in the array.
Auxiliary Space: O(N), as we are using extra space for the priority queue. Where N is the number of elements in the array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
