Maximum Median

You are given a sorted array A of N integers, where N is odd. You can make the following operation with it:

Choose one of the elements of the array (for example ai) and increase it by 1 (that is, replace it with ai + 1).</li>

Return the largest possible median of the array using at most B operations.

Note: The median of the odd-sized sorted array is the middle element after the array is sorted in non-decreasing order.


Input Format:

The first argument of input contains an integer array A, of length N.
The second argument of input contains a string B, representing the number of options.

Note: Please convert B to an integer from its string representation.

Output Format:

Return the string representation of the required maximum median.

Constraints:

1 <= N <= 1e7
1 <= A[i] <= 1e9
1<= B <= 1e12

Examples:

Input 1:
	A = [1, 3, 5]
	B = "2"

Output 1:
	"5"

Explanation 1:
	As 2nd element can be increased 2 times to make it 5.

Input 2:
	A = [1, 1, 1, 1, 2]
	B = "3"

Output 2:
	"3"

Explanation 2:
	Increase 2nd element once and fourth and last element 2 times.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Maximum Median on Interview Code Editor
Sign Up
to access hints and editorial solutions for Maximum Median

Discussion


Loading...
Click here to start solving coding interview questions