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}).
The priority queue approach is fine. But how to solve it using binary search. I tried but it gives me TLE.
You could binary search on the minimal x such that at least q_i numbers are less than or equal to x. That’s a bit more complicated and requires something like two pointers (or a second binary search), but you can try it if you want
1 Like
Thanks for replying! I tried exactly as you said, also referred the second approach mentioned in this official editorial. I have used binary search to find minimal x and then two pointers. My Solution; would be great if you can please see it. Maybe the time limit is too strict.
Yeah, actually, reading the constraints, it seems like it would be really hard to make that pass. I think you’ve written it right though - as far as I know, that’s the best binary search solution you could use.
1 Like
Thanks !