## Approach

- The first step would be to sort the array in non-decreasing order( In Java, we can use the inbuilt sort function).
- We keep increasing the median to equal its right values until it reaches the last element (largest value in array) or our operation limit or capacity is got.
- If the number of integers equals 1, i.e., n==1, then add the total capacity given into that number.
- If n>1, we will find the median calculated by finding the middle element in non-decreasing order.
- After finding the middle element, iterate through the array from mid+1 to n-1.
- For every iteration, we will try to make from mid to i-1 to i.
- After this, there will be two cases for utilizing the maximum capacity and finding the median.
- Curr variable will store the total number of operations performed on the mid to i-1 to i.
- And the ‘ans’ variable will store the maximum median of the array.

Also read, __Euclid GCD Algorithm__

## Implementation

```
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// Total capacity
long k = sc.nextLong();
long a[] = new long[n];
for(int i=0;i<n;i++){
a[i] = sc.nextLong();
}
// If the number of integers is ‘1’
if(n==1){
System.out.println(a[0]+k);
return;
}
// Sorting is non decreasing order
Arrays.sort(a);
// Finding the middle element
int mid = n/2;
// For storing the mid element
long ans = a[mid];
// Iterating through the array from the middle element to check for every operation
// that it is equal to or greater than the next right element.
for(int i=mid+1;i<n;i++){
long cur = a[i] - a[i-1];
cur = cur * 1L * (i - mid);
if(cur>=k){
System.out.println(ans + k/(i-mid));
return;
}
k -= cur;
ans += a[i] - a[i-1];
}
ans += k/(n/2+1);
System.out.println(ans);
}
}
```

## Analysis of Complexity

**Time Complexity:** The Time Complexity is O(N * log(N) + N/2) where O(N * log(N)) time is taken to sort the array and O(N/2) time to traverse the array for the median.

**Space Complexity:** The space complexity will be O(1).

## FAQs

**1). How many Sorting techniques do sort the elements?**

There are various sorting algorithms; some follow the in-place technique or divide and conquer approach.

- Insertion Sort
- Selection Sort
- Bubble Sort
- Counting Sort
- Radix Sort
- Bucket Sort
- Merge Sort
- Quick Sort
- Heap Sort

**2). What is the time complexity to solve this problem?**

The Time Complexity is O(N*logN+N/2), where N is the number of the integers in the array.

**3). What is the inbuilt function to sort the array in Java language?**

The inbuilt function to sort the array in Java language is Arrays.sort that uses dual-pivot Quicksort on **primitives.**

## Key Takeaways

In this article, we have discussed the following things:

- What the actual problem
** Median Again** is?
- Approach and Implementation to solve this problem.

Also Read - __Selection Sort in C__

Recommended Problems -

Don’t forget to practice the wide variety of DSA problems frequently asked in interview rounds readily available on __Coding Ninjas Studio__.

**Happy coding!!**