please explain the lowest sum problem
Could u please post the link
You have to take all possible pair (satisfaction and motivation ) sum and find qith smallest sum
if i do in your apporach it will give TLE
So do you want to know approach?
Bro why we not calculate 3 4 before 1 5 & 1 6
It does not matter. They all result in 7.
why ??
We have to find sum. So, it does not effect which pair you add first.
1 + 4 = 5
2 + 4 = 6
1 + 5 = 6
3 + 4 = 7
1 + 6 = 7
2 + 5 = 7
2 + 6 = 8
3 + 5 = 8
3 + 6 = 9
Even if we add 3 and 4 first then also answer is 7.
brother if we calculate ist sum 5 2nd sum 6 and third is 7 and fourth is again 6
Bro we have to find Qi th smallest element
brother is the approach is to collect all pairs having sum 5 and then 6 and then 7
Yeah kind of
and then we have calculate qi th smallest element
have you solve this question
final res vector need to be sort in order to get kth smallest number
yes
anyone make this code if not lets have a challenge to solve it first!!
Here’s the idea. q_i is small. We can directly find the first 10^4 elements of the sum sequence in order by keeping a global priority queue (min-heap) that stores, for each a_i, the values of a_i + b_j, where b_j is the minimum value in b that has not yet been summed with a_i. Keep taking the top (minimum, in this case) element from the priority queue and putting new b_j's in until you get all the elements you want. Complexity is O(T\min(K^2, 10^4)\log{K}).