Given an array arr[] of N elements and an integer K, the task is to perform at most K operation on the array. In the one operation increment any element by one of the array. Find maximize median after doing K such operation.
Example:
Input: arr[] = {1, 3, 4, 5}, K = 3
Output: 5
Explanation: Here we add two in the second element and one in the third element then we will get a maximum median. After k operation the array can become {1, 5, 5, 5}. So the maximum median we can make is ( 5 + 5 ) / 2 = 5, because here N is even.Input: arr[] = {1, 3, 6, 4, 2}, K = 10
Output: 7
Approach:
- Sort the array in increasing order.
- Since the median is the middle element of the array doing the operation in the left half then it will be worthless because it will not increase the median.
- Perform the operation in the second half and start performing the operations from the n/2th element to the end.
- If N is even then start doing the operation from the n/2 element to the end.
- Using Binary Search we will check for any number is possible as a median or not after doing K operation.
- If the median is possible then we will check for the next number which is greater than the current median calculated. Otherwise, the last possible value of the median is the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check operation can be// perform or notbool possible(int arr[], int N, int mid, int K){ int add = 0; for (int i = N / 2 - (N + 1) % 2; i < N; ++i) { if (mid - arr[i] > 0) { // Number of operation to // perform s.t. mid is median add += (mid - arr[i]); if (add > K) return false; } } // If mid is median of the array if (add <= K) return true; else return false;}// Function to find max median// of the arrayint findMaxMedian(int arr[], int N, int K){ // Lowest possible median int low = 1; int mx = 0; for (int i = 0; i < N; ++i) { mx = max(mx, arr[i]); } // Highest possible median long long int high = K + mx; while (low <= high) { int mid = (high + low) / 2; // Checking for mid is possible // for the median of array after // doing at most k operation if (possible(arr, N, mid, K)) { low = mid + 1; } else { high = mid - 1; } } if (N % 2 == 0) { if (low - 1 < arr[N / 2]) { return (arr[N / 2] + low - 1) / 2; } } // Return the max possible ans return low - 1;}// Driver Codeint main(){ // Given array int arr[] = { 1, 3, 6 }; // Given number of operation int K = 10; // Size of array int N = sizeof(arr) / sizeof(arr[0]); // Sort the array sort(arr, arr + N); // Function call cout << findMaxMedian(arr, N, K); return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{// Function to check operation can be// perform or notstatic boolean possible(int arr[], int N, int mid, int K){ int add = 0; for(int i = N / 2 - (N + 1) % 2; i < N; ++i) { if (mid - arr[i] > 0) { // Number of operation to // perform s.t. mid is median add += (mid - arr[i]); if (add > K) return false; } } // If mid is median of the array if (add <= K) return true; else return false;}// Function to find max median// of the arraystatic int findMaxMedian(int arr[], int N, int K){ // Lowest possible median int low = 1; int mx = 0; for(int i = 0; i < N; ++i) { mx = Math.max(mx, arr[i]); } // Highest possible median int high = K + mx; while (low <= high) { int mid = (high + low) / 2; // Checking for mid is possible // for the median of array after // doing at most k operation if (possible(arr, N, mid, K)) { low = mid + 1; } else { high = mid - 1; } } if (N % 2 == 0) { if (low - 1 < arr[N / 2]) { return (arr[N / 2] + low - 1) / 2; } } // Return the max possible ans return low - 1;}// Driver codepublic static void main(String[] args){ // Given array int arr[] = { 1, 3, 6 }; // Given number of operation int K = 10; // Size of array int N = arr.length; // Sort the array Arrays.sort(arr); // Function call System.out.println(findMaxMedian(arr, N, K));}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to check operation can be# perform or notdef possible(arr, N, mid, K): add = 0 for i in range(N // 2 - (N + 1) % 2, N): if (mid - arr[i] > 0): # Number of operation to # perform s.t. mid is median add += (mid - arr[i]) if (add > K): return False # If mid is median of the array if (add <= K): return True else: return False# Function to find max median# of the arraydef findMaxMedian(arr, N,K): # Lowest possible median low = 1 mx = 0 for i in range(N): mx = max(mx, arr[i]) # Highest possible median high = K + mx while (low <= high): mid = (high + low) // 2 # Checking for mid is possible # for the median of array after # doing at most k operation if (possible(arr, N, mid, K)): low = mid + 1 else : high = mid - 1 if (N % 2 == 0): if (low - 1 < arr[N // 2]): return (arr[N // 2] + low - 1) // 2 # Return the max possible ans return low - 1# Driver Codeif __name__ == '__main__': # Given array arr = [1, 3, 6] # Given number of operation K = 10 # Size of array N = len(arr) # Sort the array arr = sorted(arr) # Function call print(findMaxMedian(arr, N, K))# This code is contributed by Mohit Kumar |
C#
// C# program for the above approach using System; class GFG{ // Function to check operation can be// perform or notstatic bool possible(int []arr, int N, int mid, int K){ int add = 0; for(int i = N / 2 - (N + 1) % 2; i < N; ++i) { if (mid - arr[i] > 0) { // Number of operation to // perform s.t. mid is median add += (mid - arr[i]); if (add > K) return false; } } // If mid is median of the array if (add <= K) return true; else return false;} // Function to find max median// of the arraystatic int findMaxMedian(int []arr, int N, int K){ // Lowest possible median int low = 1; int mx = 0; for(int i = 0; i < N; ++i) { mx = Math.Max(mx, arr[i]); } // Highest possible median int high = K + mx; while (low <= high) { int mid = (high + low) / 2; // Checking for mid is possible // for the median of array after // doing at most k operation if (possible(arr, N, mid, K)) { low = mid + 1; } else { high = mid - 1; } } if (N % 2 == 0) { if (low - 1 < arr[N / 2]) { return (arr[N / 2] + low - 1) / 2; } } // Return the max possible ans return low - 1;} // Driver codepublic static void Main(string[] args){ // Given array int []arr = { 1, 3, 6 }; // Given number of operation int K = 10; // Size of array int N = arr.Length; // Sort the array Array.Sort(arr); // Function call Console.Write(findMaxMedian(arr, N, K));}} // This code is contributed by rock_cool |
Javascript
<script> // Javascript program for the above approach // Function to check operation can be // perform or not function possible(arr, N, mid, K) { let add = 0; for (let i = parseInt(N / 2, 10) - (N + 1) % 2; i < N; ++i) { if (mid - arr[i] > 0) { // Number of operation to // perform s.t. mid is median add += (mid - arr[i]); if (add > K) return false; } } // If mid is median of the array if (add <= K) return true; else return false; } // Function to find max median // of the array function findMaxMedian(arr, N, K) { // Lowest possible median let low = 1; let mx = 0; for (let i = 0; i < N; ++i) { mx = Math.max(mx, arr[i]); } // Highest possible median let high = K + mx; while (low <= high) { let mid = parseInt((high + low) / 2, 10); // Checking for mid is possible // for the median of array after // doing at most k operation if (possible(arr, N, mid, K)) { low = mid + 1; } else { high = mid - 1; } } if (N % 2 == 0) { if (low - 1 < arr[parseInt(N / 2)]) { return parseInt((arr[parseInt(N / 2)] + low - 1) / 2, 10); } } // Return the max possible ans return low - 1; } // Given array let arr = [ 1, 3, 6 ]; // Given number of operation let K = 10; // Size of array let N = arr.length; // Sort the array arr.sort(); // Function call document.write(findMaxMedian(arr, N, K)); </script> |
Output:
9
Time Complexity: O(N*log(K + M)), where M is the maximum element of the given array.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
