  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Median Again

Last Updated on March 23, 2022 by Ria Pathak Sorting

Medium

### Problem Statement (Simplified):

Find the maximum possible median of provided odd-sized array where you can increase any element by one where each increment is counted as one operation. You can do a maximum of `K` operation, where `K` is also provided.

• Median: Median of an array is the middle element of an odd-sized array if the array is sorted in non-decreasing order.

See original problem statement here

#### Test Case

``````Input:
5 2
6 7 3 1 2

Output:
5

Explanation:
On sorting array in non-decreasing order, we get array as,

1 2 3 6 7

Current median is 3, if we add 2, median becomes 5, also whole capacity has been consumed, so we print the latest median.``````

### Solving Approach :

1) We sort the array so that we can calculate the median easily.

2) We keep increasing the median to make it equal to its right values until it reaches the last element (largest value in array) or our operation limit is reached.

3) After converting median to the current right value, we add the total number of steps for every element between the median and current right elements, which make value from median to right element equal, maintaining the non-decreasing behavior of array.

4) Once capacity is reached or we reach the last element, we print array.

### Example Let array `A` be,
and, `capacity` is `2`, we sort array, so that we can get a non-decreasing sequence to find median, after sorting array, we get

Median of an odd sized array is middle element of it’s non-decreasing form, so our current median lies at index `2`, i.e. our current median is `3`.

We make current median equal to elements to it’s right, so total steps would be `A[mid+1]-A[mid]`, i.e. 1 in current test case, so our final array becomes,

We consumes 1 step in last step, so we’re left with only 1 `capacity`.

Now, our median have become `4` and middle index and element at it’s right are same now. So, we move forward toward more right of middle index, i.e. index `4` at which `5` resides.

We convert all values between median index and right index equal to the value to the current right index i.e. `5`, so total number of operations will be,

`operations = (rightIndex - middleIndex) * (A[rightIndex]-A[middleIndex])`

`operations = (4-2) * (5-4)`

`operations = 2 * 1`

`operations = 2`

Total numeber of operation required are `2`, but we are left with only `1` `capacity`, hence we skip this step, and print our current median because we cannot afford further step. So, our final median becomes `4`.

### Solutions

```
#include <stdio.h>

void merge(long long arr[], int start, int mid, int end){
long long left[mid-start+1];
long long right[end-mid];
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(long long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main() {

long long n, k;
scanf("%lld%lld",&n,&k);

long long i, arr[n+1];
for(i=1;i<=n;i++)
scanf("%lld",&arr[i]);

mergeSort(arr,1,n);
long long mid = (n+1)/2;
long long cnt = 1;
long long moves = 0;
while(moves <= k && mid <= n-1)
{
long long diff = arr[mid+1] - arr[mid];
if(moves + diff*cnt <= k)
{
moves += diff*cnt;
cnt++;
arr[mid] = arr[mid+1];
mid++;
}
else
break;
}
if(moves <= k)
{
long long left = k - moves;
arr[mid] += left/cnt;
}

printf("%lld\n",arr[mid]);

}
```
```#include <bits/stdc++.h>
using namespace std;

void merge(long long arr[], int start, int mid, int end){
long long left[mid-start+1]={0};
long long right[end-mid]={0};
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(long long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main() {

long long n, k;
cin>> n>> k;

long long i, arr[n+1];
for(i=1;i<=n;i++)
cin>>arr[i];

mergeSort(arr,1,n);
long long mid = (n+1)/2;
long long cnt = 1;
long long moves = 0;
while(moves <= k && mid <= n-1)
{
long long diff = arr[mid+1] - arr[mid];
if(moves + diff*cnt <= k)
{
moves += diff*cnt;
cnt++;
arr[mid] = arr[mid+1];
mid++;
}
else
break;
}
if(moves <= k)
{
long long left = k - moves;
arr[mid] += left/cnt;
}

cout<<arr[mid]<<'\n';

}
```
```import java.util.*;
import java.io.*;

public class Main {

static void merge(long arr[], int start, int mid, int end){
long left[] = new long[mid-start+1];
long right[] = new long[end-mid];

for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

static void mergeSort(long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();

int i;
long arr[] = new long[n+1];
for(i=1;i<=n;i++)
arr[i] = sc.nextLong();

mergeSort(arr,1,n);
int mid = (n+1)/2;
long cnt = 1;
long moves = 0;
while(moves <= k && mid <= n-1)
{
long diff = arr[mid+1] - arr[mid];
if(moves + diff*cnt <= k)
{
moves += diff*cnt;
cnt++;
arr[mid] = arr[mid+1];
mid++;
}
else
break;
}
if(moves <= k)
{
long left = k - moves;
arr[mid] += left/cnt;
}

System.out.println(arr[mid]);

}
}
```

Space Complexity : O(1)

[forminator_quiz id="1347"]

This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.