# Maximize the product of sum and least power by choosing at most K elements from given value and power Arrays

Given two arrays **arr[] **and **powr[] **of size** N **and an integer **K**. Every element **arr[i]** has its respective power **powr[i]**. The task is to **maximize** the value of the given function by choosing **at most K** elements from the array. The function is defined as :

f(N) = (arr[i

_{1}] + arr[i_{2}] + arr[i_{3}]+…..arr[i_{n}]) * min(powr[i_{1}], powr[i_{2}], powr[i_{3}], …..powr[i_{n}]) where, arr[i_{1}], arr[i_{2}], arr[i_{3}], …..arr[i_{n}] are the chosen elements.Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the

Essential Maths for CP Courseat a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.

**Examples:**

Input:arr[] = {11, 10, 7, 6, 9}, powr[] = {3, 2, 4, 1, 1}, K = 2, N = 5Output:54Explanation:Choose elements at indices {0, 2} so, f(N) = (11 + 7) * min(3, 4) = 18 * 3 = 54, which is the maximum possible value that can be achieved by choosing at most 2 elements.

Input:arr[] = {5, 12, 11, 9}, powr[] = {2, 1, 10, 1}, K = 3, N = 4Output:110

**Approach: **The idea is to consider every** ith** element as the minimum power, for this, sort the elements in descending order of power, so the first element will be considered to have the highest power. All times try to maintain a list of elements of size at most** K**. This list will contain at most** K **elements with the **largest** one, not including the current **ith** element. If already have a list of size** K**, then remove the element with the smallest length so, size becomes **K – 1**, then include the current element into the list, size becomes **K**, and update **res** with maximum one. In the end, return **res** which is the answer.

- Initialize a vector of pairs
**v[]**of size**N**to store elements along with their power. - Iterate over the range
**[0, N)**using the variable**i**and perform the following tasks:- Assign the values
**power[i]**and**arr[i]**as the first and second values of the array**v[].**

- Assign the values
- Sort the array
**v[]**in ascending order. - Initialize the variables
**res**and**sum**as**0**to store the result and the sum. - Initialize a set of pairs
**s[]****.** - Iterate over the range
**[N-1, 0]**using the variable**i**and perform the following tasks:- Insert the pair
**{v[i].second, i}**into the set**s[].** - Add the value of
**v[i].second**to the variable**sum.** - If
**s.size()**is greater than**K**then perform the following tasks:- Initialize the variable
**it**as the first element of the set**s[].** - Reduce the value
**it.first**from the variable**sum.** - Remove the variable
**it**from the set**s[].**

- Initialize the variable
- Set the value of
**res**as the maximum of**res**or**sum*v[i].first.**

- Insert the pair
- After performing the above steps, print the value of
**res**as the answer.

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to maximize the value of the` `// function by choosing at most K elements` `// from the given array` `int` `maximumValue(` `int` `arr[], ` `int` `powr[],` ` ` `int` `K, ` `int` `N)` `{` ` ` `// Vector to store the power of elements` ` ` `// along with the elements in pair` ` ` `vector<pair<` `int` `, ` `int` `> > v(N);` ` ` `// In a pair, the first position contains` ` ` `// the power and the second position` ` ` `// contains the element` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `v[i].first = powr[i];` ` ` `v[i].second = arr[i];` ` ` `}` ` ` `// Sort the vector according to the` ` ` `// power of the elements` ` ` `sort(v.begin(), v.end());` ` ` `// Variable to store the answer` ` ` `int` `res = 0;` ` ` `// Variable to store the sum of` ` ` `// elements` ` ` `int` `sum = 0;` ` ` `// Create a set of pairs` ` ` `set<pair<` `int` `, ` `int` `> > s;` ` ` `// Traverse the vector in reverse order` ` ` `for` `(` `int` `i = N - 1; i >= 0; i--) {` ` ` `// Insert the element along with the` ` ` `// index in pair` ` ` `s.insert(make_pair(v[i].second, i));` ` ` `sum += v[i].second;` ` ` `// If size of set exceeds K, then` ` ` `// delete the first pair in the set` ` ` `// and update the sum by excluding` ` ` `// the elements value from it` ` ` `if` `(s.size() > K) {` ` ` `auto` `it = s.begin();` ` ` `sum -= it->first;` ` ` `s.erase(it);` ` ` `}` ` ` `// Store the maximum of all sum` ` ` `// multiplied by the element's` ` ` `// power` ` ` `res = max(res, sum * v[i].first);` ` ` `}` ` ` `// Return res` ` ` `return` `res;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 11, 10, 7, 6, 9 };` ` ` `int` `powr[] = { 3, 2, 4, 1, 1 };` ` ` `int` `K = 2;` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << maximumValue(arr, powr, K, N);` ` ` `return` `0;` `}` |

## Python3

`# Python 3 program for the above approach` `# Function to maximize the value of the` `# function by choosing at most K elements` `# from the given array` `def` `maximumValue(arr, powr, K, N):` ` ` `# Vector to store the power of elements` ` ` `# along with the elements in pair` ` ` `v ` `=` `[[` `0` `for` `x ` `in` `range` `(` `2` `)] ` `for` `y ` `in` `range` `(N)]` ` ` `# In a pair, the first position contains` ` ` `# the power and the second position` ` ` `# contains the element` ` ` `for` `i ` `in` `range` `(N):` ` ` `v[i][` `0` `] ` `=` `powr[i]` ` ` `v[i][` `1` `] ` `=` `arr[i]` ` ` `# Sort the vector according to the` ` ` `# power of the elements` ` ` `v.sort()` ` ` `# Variable to store the answer` ` ` `res ` `=` `0` ` ` `# Variable to store the sum of` ` ` `# elements` ` ` `sum` `=` `0` ` ` `# Create a set of pairs` ` ` `s ` `=` `set` `([])` ` ` `# Traverse the vector in reverse order` ` ` `for` `i ` `in` `range` `(N ` `-` `1` `, ` `-` `1` `, ` `-` `1` `):` ` ` `# Insert the element along with the` ` ` `# index in pair` ` ` `s.add((v[i][` `1` `], i))` ` ` `sum` `+` `=` `v[i][` `1` `]` ` ` `# If size of set exceeds K, then` ` ` `# delete the first pair in the set` ` ` `# and update the sum by excluding` ` ` `# the elements value from it` ` ` `if` `(` `len` `(s) > K):` ` ` `sum` `-` `=` `list` `(s)[` `0` `][` `0` `]` ` ` `list` `(s).remove(` `list` `(s)[` `0` `])` ` ` `# Store the maximum of all sum` ` ` `# multiplied by the element's` ` ` `# power` ` ` `res ` `=` `max` `(res, ` `sum` `*` `v[i][` `0` `])` ` ` `# Return res` ` ` `return` `res` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `arr ` `=` `[` `11` `, ` `10` `, ` `7` `, ` `6` `, ` `9` `]` ` ` `powr ` `=` `[` `3` `, ` `2` `, ` `4` `, ` `1` `, ` `1` `]` ` ` `K ` `=` `2` ` ` `N ` `=` `len` `(arr)` ` ` `print` `(maximumValue(arr, powr, K, N))` ` ` `# This code is contributed by ukasp.` |

## Javascript

`<script>` `// Javascript program for the above approach` `// Function to maximize the value of the` `// function by choosing at most K elements` `// from the given array` `function` `maximumValue(arr, powr, K, N) {` ` ` `// Vector to store the power of elements` ` ` `// along with the elements in pair` ` ` `let v = ` `new` `Array(N).fill(0).map(() => []);` ` ` `// In a pair, the first position contains` ` ` `// the power and the second position` ` ` `// contains the element` ` ` `for` `(let i = 0; i < N; i++) {` ` ` `v[i][0] = powr[i];` ` ` `v[i][1] = arr[i];` ` ` `}` ` ` `// Sort the vector according to the` ` ` `// power of the elements` ` ` `v.sort();` ` ` `// Variable to store the answer` ` ` `let res = 0;` ` ` `// Variable to store the sum of` ` ` `// elements` ` ` `let sum = 0;` ` ` `// Create a set of pairs` ` ` `let s = ` `new` `Set();` ` ` `// Traverse the vector in reverse order` ` ` `for` `(let i = N - 1; i >= 0; i--) {` ` ` `// Insert the element along with the` ` ` `// index in pair` ` ` `s.add([v[i][1], i]);` ` ` `sum += v[i][1];` ` ` `// If size of set exceeds K, then` ` ` `// delete the first pair in the set` ` ` `// and update the sum by excluding` ` ` `// the elements value from it` ` ` `if` `(s.size > K) {` ` ` `let it = [...s][0];` ` ` `sum -= it[0];` ` ` `s.` `delete` `(it);` ` ` `}` ` ` `// Store the maximum of all sum` ` ` `// multiplied by the element's` ` ` `// power` ` ` `res = Math.max(res, sum * v[i][0]);` ` ` `}` ` ` `// Return res` ` ` `return` `res;` `}` `// Driver Code` `let arr = [11, 10, 7, 6, 9];` `let powr = [3, 2, 4, 1, 1];` `let K = 2;` `let N = arr.length;` `document.write(maximumValue(arr, powr, K, N))` `// This code is contributed by saurabh_jaiswal.` `</script>` |

**Output**

54

**Time Complexity: **O(NlogN)**Auxiliary Space: **O(N)