We have 2 arrays $$$A$$$ and $$$B$$$ of length $$$n$$$ each. We are required to pick $$$k$$$ elements from both the arrays say $$$A_{i_{1}}, A_{i_{2}}, ... A_{i_{k}}$$$ and $$$B_{i_{1}}, B_{i_{2}}, ... B_{i_{k}}$$$ such that the sum $$$A_{i_{1}} + A_{i_{2}} + ... + A_{i_{k}} > \lfloor{\frac{S_{A}}{2}}\rfloor$$$ and $$$B_{i_{1}} + B_{i_{2}} + ... + B_{i_{k}} > \lfloor{\frac{S_{B}}{2}}\rfloor$$$. Here $$$S_{A}$$$ and $$$S_{B}$$$ denote the sum of the arrays A and B respectively.$$$\newline$$$ We also want to print the indices we have chosen, if such a choice is possible.$$$\newline$$$ Also, pay attention to the fact that we are picking elements from $$$B$$$ with the same indices $$${i_{1}, i_{2}, ... , i_{k}}$$$ that we have used for $$$A$$$.$$$\newline$$$ **Constraints** :- $$$A_{i}, B_{i} \le 10^{9}$$$ and, size of the arrays $$$\le 10^{5}$$$. Please can anyone help me in solving this??

use priority queue or just sort the array to pick the K largest element from the array

That simply won't work as we need to pick the elements at the same set of indices from $$$B$$$ which we have chosen from $$$A$$$

ohh , I missed that

Can you send the link to this problem?

Sorry, I don't have the link, an interviewer asked me in a coding interview.

Not sure if this solution works, but here it is:

Let Sa = sum of all elements of

A, divided by two.Similarly, Sb = sum of all elements of

Bdivided by two.In beginning, choose the max

Knumbers from array A. If their sum is smaller than Sa, the answer obviously does not exist. Otherwise, run a While loop, in condition: while the sum of chosen elements of B is smaller than the desired sum (that is, Sb), find an initially chosen index i, such that it has the least value ofAi. (Notethat once we change this i, we cant change it anymore). Then set that index to the position of the highest value of B that we haven't chosen that position yet, update the answer and check again if the current sum of chosen elements is≥ Sb. Keep doing this until the answer is not found. If at some point inside the While, sum of chosen elements of A becomes less than Sa, then the answer doesn't exist.try something like the trick from time is money:

let $$$f(i) = lambda * a[i] + (1 - lambda) * b[i]$$$

if we take the indices that score the biggest $$$k$$$ values of $$$f$$$, this will obviously maximize sum of $$$A$$$s for $$$lambda = 1$$$ and maximize sum of $$$B$$$s for $$$lambda = 0$$$. The more $$$lambda$$$ increases the more we care about $$$B$$$s. If we binary search $$$lambda$$$ such that the algo cares enough about $A$s to get a sum of $A$s big enough, the resulting sum of $B$s should be the theoretical maximum.