Given an integer array of size n and a number k. If the indexing is 1 based then the middle element of the array is the element at index (n + 1) / 2, if n is odd otherwise n / 2. The task is to delete exactly k elements from the array in such a way that the middle element of the reduced array is as maximum as possible. Find the maximum possible middle element of the array after deleting exactly k elements.
Examples:
Input :
n = 5, k = 2
arr[] = {9, 5, 3, 7, 10};
Output : 7
Input :
n = 9, k = 3
arr[] = {2, 4, 3, 9, 5, 8, 7, 6, 10};
Output : 9
In the first input, if we delete 5 and 3 then the array becomes {9, 7, 10} and
the middle element will be 7.
In the second input, if we delete one element before 9 and two elements after 9
(for example 2, 5, 8) then the array becomes {4, 3, 9, 7, 6, 10} and middle
element will be 9 and it will be the optimum solution.
Naive Approach :
The naive approach is to check all possible solutions. There could be C(n, k) possible solutions. If we check all possible solutions to find an optimal solution, it will consume a lot of time.
Optimal Approach :
After deleting k elements, the array will be reduced to size n – k. Since we can delete any k numbers from the array to find the maximum possible middle elements. If we note, the index of the middle element after deleting k elements will lie in the range ( n + 1 – k ) / 2 and ( n + 1 – k ) / 2 + k. So in order to find the optimal solution, simply iterate the array from the index ( n + 1 – k ) / 2 to index ( n + 1 – k ) / 2 + k and select the maximum element in this range.
The is the implementation is given below.
C++
#include <bits/stdc++.h>using namespace std;// Function to calculate maximum possible middle // value of the array after deleting exactly k // elementsint maximum_middle_value(int n, int k, int arr[]){ // Initialize answer as -1 int ans = -1; // Calculate range of elements that can give // maximum possible middle value of the array // since index of maximum possible middle // value after deleting exactly k elements from // array will lie in between low and high int low = (n + 1 - k) / 2; int high = (n + 1 - k) / 2 + k; // Find maximum element of the array in // range low and high for (int i = low; i <= high; i++) { // since indexing is 1 based so // check element at index i - 1 ans = max(ans, arr[i - 1]); } // Return the maximum possible middle value // of the array after deleting exactly k // elements from the array return ans;}// Driver Codeint main(){ int n = 5, k = 2; int arr[] = { 9, 5, 3, 7, 10 }; cout << maximum_middle_value(n, k, arr) << endl; n = 9; k = 3; int arr1[] = { 2, 4, 3, 9, 5, 8, 7, 6, 10 }; cout << maximum_middle_value(n, k, arr1) << endl; return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG{// Function to calculate maximum possible middle // value of the array after deleting exactly k // elements static int maximum_middle_value(int n, int k, int arr[]) { // Initialize answer as -1 int ans = -1; // Calculate range of elements that can give // maximum possible middle value of the array // since index of maximum possible middle // value after deleting exactly k elements from // array will lie in between low and high int low = (n + 1 - k) / 2; int high = (n + 1 - k) / 2 + k; // Find maximum element of the array in // range low and high for (int i = low; i <= high; i++) { // since indexing is 1 based so // check element at index i - 1 ans = Math.max(ans, arr[i - 1]); } // Return the maximum possible middle value // of the array after deleting exactly k // elements from the array return ans; } // Driver Code public static void main(String args[]) { int n = 5, k = 2; int arr[] = { 9, 5, 3, 7, 10 }; System.out.println( maximum_middle_value(n, k, arr)); n = 9; k = 3; int arr1[] = { 2, 4, 3, 9, 5, 8, 7, 6, 10 }; System.out.println( maximum_middle_value(n, k, arr1)); } }// This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach# Function to calculate maximum possible # middle value of the array after # deleting exactly k elements def maximum_middle_value(n, k, arr): # Initialize answer as -1 ans = -1 # Calculate range of elements that can give # maximum possible middle value of the array # since index of maximum possible middle # value after deleting exactly k elements # from array will lie in between low and high low = (n + 1 - k) // 2 high = (n + 1 - k) // 2 + k # Find maximum element of the # array in range low and high for i in range(low, high+1): # since indexing is 1 based so # check element at index i - 1 ans = max(ans, arr[i - 1]) # Return the maximum possible middle # value of the array after deleting # exactly k elements from the array return ans # Driver Code if __name__ == "__main__": n, k = 5, 2 arr = [9, 5, 3, 7, 10] print(maximum_middle_value(n, k, arr)) n, k = 9, 3 arr1 = [2, 4, 3, 9, 5, 8, 7, 6, 10] print(maximum_middle_value(n, k, arr1)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System;class GFG{ // Function to calculate maximum possible middle // value of the array after deleting exactly k // elements static int maximum_middle_value(int n, int k, int []arr) { // Initialize answer as -1 int ans = -1; // Calculate range of elements that can give // maximum possible middle value of the array // since index of maximum possible middle // value after deleting exactly k elements from // array will lie in between low and high int low = (n + 1 - k) / 2; int high = (n + 1 - k) / 2 + k; // Find maximum element of the array in // range low and high for (int i = low; i <= high; i++) { // since indexing is 1 based so // check element at index i - 1 ans = Math.Max(ans, arr[i - 1]); } // Return the maximum possible middle value // of the array after deleting exactly k // elements from the array return ans; } // Driver Code static public void Main (){ int n = 5, k = 2; int []arr = { 9, 5, 3, 7, 10 }; Console.WriteLine( maximum_middle_value(n, k, arr)); n = 9; k = 3; int []arr1 = { 2, 4, 3, 9, 5, 8, 7, 6, 10 }; Console.WriteLine( maximum_middle_value(n, k, arr1)); } }// This code is contributed by ajit. |
Javascript
<script>// Function to calculate maximum possible middle // value of the array after deleting exactly k // elements function maximum_middle_value(n, k, arr) { // Initialize answer as -1 let ans = -1; // Calculate range of elements that can give // maximum possible middle value of the array // since index of maximum possible middle // value after deleting exactly k elements from // array will lie in between low and high let low = Math.floor((n + 1 - k) / 2); let high = Math.floor(((n + 1 - k) / 2) + k); // Find maximum element of the array in // range low and high for (let i = low; i <= high; i++) { // since indexing is 1 based so // check element at index i - 1 ans = Math.max(ans, arr[i - 1]); } // Return the maximum possible middle value // of the array after deleting exactly k // elements from the array return ans; } // Driver Code let n = 5, k = 2; let arr = [ 9, 5, 3, 7, 10 ]; document.write(maximum_middle_value(n, k, arr) + "<br>"); n = 9; k = 3; let arr1 = [ 2, 4, 3, 9, 5, 8, 7, 6, 10 ]; document.write(maximum_middle_value(n, k, arr1) + "<br>"); // This code is contributed by Mayank Tyagi</script> |
Output:
7 9
Time Complexity: O(high-low), where high and low are the terms calculated
Auxiliary Space: O(1), as no extra space is used
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!