Median Again

Soumya Agrawal
Last Updated: May 13, 2022

 

Introduction

 

Sorting is a technique of arranging items in a particular order—the most used method for solving complex problems. Various sorting algorithms like Insertion Sort, Selection Sort, and many more are based on different time and space complexities.

 

The Median Again problem states to define the median in an array with some conditions that we will discuss in our problem statement.

 

Problem Statement

We are given a set of ‘N’ integers in an array in which we have to perform one operation at most ‘k’ times.  The operation is that for some index ‘i’, we have increment ai by ‘1’. With this operation, we have to maximize the median.

Note: The number of integers(N) will be odd.

How to find the median of odd integers?

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

 

Example:

Input:

5 2

6 7 3 1 2

 

Output:

5

 

1 2 3 6 7

 

The current median is 3. If we add 2, the median becomes 5; the total capacity has been consumed, so we print the latest median.

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.

 

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.

 

Keep in mind the various sorting algorithms required for some problems.

 

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

 

Happy coding!!

 

Was this article helpful ?
0 upvotes