Last Updated on March 23, 2022 by Ria Pathak
Concepts Used
Sorting
Difficulty Level
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
Koperation, whereKis 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
Abe,
and,capacityis2, we sort array, so that we can get a non-decreasing sequence to find median, after sorting array, we getMedian 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 is3.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
4and middle index and element at it’s right are same now. So, we move forward toward more right of middle index, i.e. index4at which5resides.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 = 2Total numeber of operation required are
2, but we are left with only1capacity, hence we skip this step, and print our current median because we cannot afford further step. So, our final median becomes4.
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.