Minimize the maximum of Array by replacing any element with other element at most K times
Given an array arr[] of size N and an integer K, the task is to minimize the value of the maximum element of the array arr[] after replacing any element of the array with any other element of that array at most K times.
Examples:
Input: arr[] = {5, 3, 3, 2, 1}, K = 3
Output: 2
Explanation: Replace the elements at index 0, 1 and 2 with the value 1.
The array becomes {1, 1, 1, 2, 1}. The maximum is 2.
This is the minimum possible maximum.Input: arr[] = {1, -2, 3}, K = 2
Output: -2
Approach: The problem can be solved using the concept of Hash map based on the following idea:
If number of elements with value greater than any array elements arr[i] is K and arr[i] is the largest element fulfilling this criteria, then with at most K replacements all those values can be made at least equal to arr[i].
Follow the below illustration for a better understanding.
Illustration:
Consider arr[] = {5, 3, 3, 2, 1}, K = 3
For element 5:
=> Number of elements greater than or equal to 5 is 1.
=> K > 1For element 3:
=> Number of elements greater than or equal to 3 is 3.
=> K ≥ 3. So not this. Because this can be converted to some other elementFor element 2:
=> Number of elements greater than or equal to 2 is 4.
=> K < 4. This is the highest such element which satisfies the criteria.So 2 is the answer.
Follow the below steps to solve the problem:
- If K = 0, then replacement of any element is not possible, then maximum element of the array remains same.
- If K ≥ N – 1, then replace all elements with the minimum element, so the maximum can be made to be the same as minimum of array.
- Else, use a map to store the count of occurrences of an element of the array.
- Traverse from the highest value of the array:
- If the count of the element is less than K, decrement K by the count.
- Otherwise, that element is the minimum possible maximum value.
- Return the value of the minimum possible maximum value.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to minimize the maximum // element of the array int minimizeMax( int * arr, int N, int K) { int Ans; // If K >= (N - 1), then maximum // element changes to minimum // element of array if (K >= (N - 1)) { Ans = INT_MAX; for ( int i = 0; i < N; i++) Ans = min(Ans, arr[i]); } // If K==0, then maximum element // remains same else if (K == 0) { Ans = INT_MIN; for ( int i = 0; i < N; i++) Ans = max(Ans, arr[i]); } else { map< int , int > mp; for ( int i = 0; i < N; i++) { mp[arr[i]]++; } // Create a map reverse iterator map< int , int >::reverse_iterator it; // Traverse map from reverse and // if K >= Count of current // element then subtract it from // k and move to next element // else return the element for (it = mp.rbegin(); it != mp.rend(); it++) { if (K >= it->second) K -= it->second; else return it->first; } } // If any of first two conditions // satisfied then return Ans return Ans; } // Driver Code int main() { int arr[] = { 5, 3, 3, 2, 1 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 3; // Function call cout << minimizeMax(arr, N, K) << endl; return 0; } |
Java
// Java code to implement the above approach import java.io.*; import java.util.*; class GFG { // Function to minimize the maximum // element of the array public static int minimizeMax( int arr[], int N, int K) { int ans = 0 ; // If K >= (N - 1), then maximum // element changes to minimum // element of array if (K >= (N - 1 )) { ans = Integer.MAX_VALUE; for ( int i = 0 ; i < N; i++) ans = Math.min(ans, arr[i]); } // If K==0, then maximum element // remains same else if (K == 0 ) { ans = Integer.MIN_VALUE; for ( int i = 0 ; i < N; i++) ans = Math.max(ans, arr[i]); } else { // Creating a map in descending order of keys TreeMap<Integer, Integer> mp = new TreeMap<>(Collections.reverseOrder()); for ( int i = 0 ; i < N; i++) { if (mp.get(arr[i]) != null ) mp.put(arr[i], mp.get(arr[i]) + 1 ); else mp.put(arr[i], 1 ); } // Traverse map and // if K >= Count of current // element then subtract it from // k and move to next element // else return the element for (Map.Entry<Integer, Integer> ele : mp.entrySet()) { if (K >= ele.getValue()) K -= ele.getValue(); else return ele.getKey(); } } // If any of first two conditions // satisfied then return Ans return ans; } public static void main(String[] args) { int arr[] = { 5 , 3 , 3 , 2 , 1 }; int N = 5 ; int K = 3 ; // Function call System.out.println(minimizeMax(arr, N, K)); } } // This code is contributed by Rohit Pradhan. |
Python3
# Python code to implement the above approach # Function to minimize the maximum # element of the array def minimizeMax(arr, N, K): Ans = 0 # If K >= (N - 1), then maximum # element changes to minimum # element of array if (K > = (N - 1 )): Ans = sys.maxsize for i in range ( 0 , N): Ans = min (Ans, arr[i]) # If K==0, then maximum element # remains same elif (K = = 0 ): Ans = - 1 * sys.maxsize for i in range ( 0 , N): Ans = max (Ans, arr[i]) else : mp = dict () for i in range (N): if arr[i] in mp.keys(): mp[arr[i]] + = 1 else : mp[arr[i]] = 1 # Traverse map from reverse and # if K >= Count of current # element then subtract it from # k and move to next element # else return the element for x in mp: if (K > = mp[x]): K - = mp[x] else : return x # If any of first two conditions # satisfied then return Ans return Ans # Driver Code arr = [ 5 , 3 , 3 , 2 , 1 ] N = len (arr) K = 3 # Function call print (minimizeMax(arr, N, K)) # This code is contributed by Taranpreet |
C#
// C# code to implement the above approach using System; using System.Collections.Generic; public class GFG { // Function to minimize the maximum // element of the array public static int minimizeMax( int [] arr, int N, int K) { int ans = 0; // If K >= (N - 1), then maximum // element changes to minimum // element of array if (K >= (N - 1)) { ans = Int32.MaxValue; for ( int i = 0; i < N; i++) ans = Math.Min(ans, arr[i]); } // If K==0, then maximum element // remains same else if (K == 0) { ans = Int32.MinValue; for ( int i = 0; i < N; i++) ans = Math.Max(ans, arr[i]); } else { // Creating a map Dictionary< int , int > mp = new Dictionary< int , int >(); for ( int i = 0; i < N; i++) { if (!mp.ContainsKey(arr[i])) mp[arr[i]] = 0; mp[arr[i]]++; } // Traverse map from reverse and // if K >= Count of current // element then subtract it from // k and move to next element // else return the element foreach ( var x in mp) { if (K >= x.Value) K -= x.Value; else return x.Key; } } // If any of first two conditions // satisfied then return Ans return ans; } public static void Main( string [] args) { int [] arr = { 5, 3, 3, 2, 1 }; int N = 5; int K = 3; // Function call Console.WriteLine(minimizeMax(arr, N, K)); } } // This code is contributed by phasing17 |
Javascript
<script> // JavaScript program for above approach // Function to minimize the maximum // element of the array function minimizeMax(arr,N,K) { let Ans; // If K >= (N - 1), then maximum // element changes to minimum // element of array if (K >= (N - 1)) { Ans = Number.MAX_VALUE; for (let i = 0; i < N; i++) Ans = Math.min(Ans, arr[i]); } // If K==0, then maximum element // remains same else if (K == 0) { Ans = Number.MIN_VALUE; for (let i = 0; i < N; i++) Ans = Math.max(Ans, arr[i]); } else { let mp = new Map(); for (let i = 0; i < N; i++) { if (mp.has(arr[i])){ mp.set(arr[i],mp.get(arr[i])+1); } else mp.set(arr[i],1); } // Traverse map from reverse and // if K >= Count of current // element then subtract it from // k and move to next element // else return the element for (let [x,y] of mp){ if (K >= mp.get(x)) K -= mp.get(x) else return x } } // If any of first two conditions // satisfied then return Ans return Ans; } // Driver Code let arr = [ 5, 3, 3, 2, 1 ]; let N = arr.length; let K = 3; // Function call document.write(minimizeMax(arr, N, K), "</br>" ); // This code is contributed by shinjanpatra </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)