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 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 by learning Master algorithms online.

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]);

  }
}

where N is the size of array

Space Complexity : O(1)

Previous post The Last Game
Next post Shortest cycle(Minor image correction “ex 2”)

Leave a Reply

Your email address will not be published. Required fields are marked *