You are given an array consisting of N integers. Now you can perform one type of operation on it which is to choose any index i and increment ai by 1 i.e. ai=ai+1. With this operation, you want to maximize the median. Also, you can apply this operation at most K times. The median of the odd-sized array is the middle element after the array is sorted in non-decreasing order.
input: 3 2
1 3 5
output: 5
input: 5 5
1 2 1 1 1
output: 3
I am having a hard time understanding the problem, My thoughts are, they have asked for the maximum median and if we just sort and pick the middle element and increase it with k. Then it would be the maximum median. I've seen some solutions on the internet but I couldn't understand them. Can someone help me out with what to do here?
My thoughts are, they have asked for the maximum median and if we just sort and pick the middle element and increase it with k. Then it would be the maximum median.
Not really, because once it's incremented that element may very well not be the median anymore. Consider the example 1, 2, 1, 1, 1. The median is 1 (sorted: 1, 1, 1, 1, 2) and if you add all of k = 5 to that element, you'll obtain 1, 1, 6, 1, 2 -> 1, 1, 1, 2, 6. The median would still be 1, which is "wrong".
Try the following algorithm, instead.
Sort the N integers. Once, at the beginning, so that you can easily find the median (it's the element in the middle or the mean of the two conseuctive middle elements in case of N even). Now you can forget about all the elements less than the median (again, if N is even, you need to keep one of those).
Find the first element greater than the median. In the previous example, we would have 1, 1, 2, so that there are 2 elements (let's call it m) equal to the median and the 2 is the first one greater than that.
To be able to increase the median of at least one, we should consume at least m out of k (by literally subtracting m from k), ideally, adding 1 to each of the elements equal to the median (that element included) -> 2, 2, 2 (yes, the whole array would be 1, 1, 2, 2, 2, but again, ignore the smaller values), so that the median now is 2.
Now there are 3 elements, all equal, and to increase the median by one, we have to consume 3 out of k. We can go on as long as k stay positive.
If k is not enough to "fill" the gap (when k < m), we need to stop and the median can't be increased any futher. E.g. in the previous example the steps are: k = 5, 1, 1, 2, m = 2 -> k = 3, 2, 2, 2, m = 3 -> k = 0, 3, 3, 3 -> max median = 3;