Given an array arr[] of N integers and an integer K, where K denotes the maximum number of operations which can be applied to the array, the task is to maximize the minimum value of arr[] by using the given operation at most K times.
- In one operation it is possible to select any element of the given arr[] and can change it with its adjacent element.
Examples:
Input: N = 7, K = 4, arr[] = {9, 7, 3, 5, 7, 8, 7}
Output: 7
Explanation: First operation: Change 3 at index 2 with 7 at index 1.
So the arr[] becomes: {9, 7, 7, 5, 7, 8, 7}
Second Operation: Change 5 at index 3 with 7 at index 2.
So the arr[] becomes: {9, 7, 7, 7, 7, 8, 7}
Third operation: Change 7 at index 6 with 8 at index 5.
So the arr[] becomes: {9, 7, 7, 7, 7, 8, 8}
Fourth Operation: Change 7 at index 1 with 9 at index 0.
So the arr[] becomes: {9, 9, 7, 7, 7, 8, 8}
The minimum value in arr[] after applying operation at most K times is: 7Input: N = 4, K = 2, arr[] = {2, 5, 6, 8}
Output: 6
Explanation: First operation: Change 5 at index 1 with 6 at index 2.
So that the arr[] becomes: {2, 6, 6, 8}
Second operation: Change 2 at index 0 with 6 at index 1.
So that the arr[] becomes: {6, 6, 6, 8}
The minimum value of arr[] can be achieved by applying operations is: 6
Approach: To solve the problem follow the below idea:
Sort the arr[], if K is greater than or equal to length of arr[], simply return element at last index of arr[] else return element at Kth index of arr[].
Illustration with an Example:
Consider N = 6, K = 3, arr[] = {9, 7, 3, 1, 2, 5}
We can perform the following operations
Operation 1:- Change 2 at index 4 with 5 at index 5 . So the arr[] becomes: {9, 7, 3, 1, 5, 5}
Operation 2:- Change 1 at index 3 with 5 at index 4 . So the arr[] becomes: {9, 7, 3, 5, 5, 5}
Operation 3:- Change 3 at index 2 with 7 at index 1 . So the arr[] becomes: {9, 7, 7, 5, 5, 5}
Minimum element after applying operation at most 3 times is: 5When you will sort the arr[] and return arr[K] you will get the same output :-
Sorted arr[]: {1, 2, 3, 5, 7, 9}
arr[K] = arr[3] = 5, which is out required answer.
Follow the steps to solve the problem:
- Sort the array.
- Check if K is greater than or equal to arr[] or not.
- If yes, then simply return the element at the last index of arr[].
- Else return the element at the Kth index of arr[].
- Print the output.
Below is the implementation for the above approach:
C++
// C++ code to implement the approach.#include <bits/stdc++.h>using namespace std;int main() { int N = 6, K = 3 ; int arr[] = { 9, 1, 3, 7, 2, 5 } ; // Sorting the Array sort( arr, arr+N ) ; // Condition when K is greater than // or equal to length of arr[] then // returning element at last // index of arr[] if( K >= N ) cout << arr[ N-1 ] ; // if K is less than length of // arr[] then returning element at Xth position else cout << arr[ K ] ; return 0;}// This code is contributed by rahulbhardwaj0711. |
Java
// Java code to implement the approach.import java.util.*;class GFG { // Driver code public static void main(String[] args) { int N = 6, K = 3; int[] arr = { 9, 7, 3, 1, 2, 5 }; // Function call System.out.println(Min_Value(N, K, arr)); } // Function which is called in main() static int Min_Value(int N, int K, int arr[]) { // Sorting arr[] with inbuilt sort // function in Arrays class Arrays.sort(arr); // Condition when K is greater than // or equal to length of arr[] then // returning element at last // index of arr[] if (K == arr.length || K > arr.length) return (arr[arr.length - 1]); // if K is less than length of // arr[] then returning // element at Xth position else return (arr[K]); }} |
Python3
# python3 code to implement the approach.if __name__ == "__main__": N = 6 K = 3 arr = [9, 1, 3, 7, 2, 5] # Sorting the Array arr.sort() # Condition when K is greater than # or equal to length of arr[] then # returning element at last # index of arr[] if(K >= N): print(arr[N-1]) # if K is less than length of # arr[] then returning element at Xth position else: print(arr[K]) # This code is contributed by rakeshsahni |
C#
// C# code to implement the approach.using System;public class GFG { static public void Main() { // Code int N = 6, K = 3; int[] arr = { 9, 7, 3, 1, 2, 5 }; // Function call Console.WriteLine(Min_Value(N, K, arr)); } // Function which is called in main() static int Min_Value(int N, int K, int[] arr) { // Sorting arr[] with inbuilt sort // function in Arrays class Array.Sort(arr); // Condition when K is greater than // or equal to length of arr[] then // returning element at last // index of arr[] if (K == arr.Length || K > arr.Length) return (arr[arr.Length - 1]); // if K is less than length of // arr[] then returning // element at Xth position else return (arr[K]); }}// This code is contributed by lokeshmvs21. |
Javascript
<script> let N = 6, K = 3; let arr = [9, 1, 3, 7, 2, 5]; // Sorting the Array arr.sort(); // Condition when K is greater than // or equal to length of arr[] then // returning element at last // index of arr[] if( K >= N ) document.write(arr[N-1],"</br>"); // if K is less than length of // arr[] then returning element at Xth position else document.write(arr[K],"</br>"); // This code is contributed by Rohit Pradhan </script> |
5
Time Complexity: O(N * logN), because sorting is performed.
Auxiliary Space: O(1), as no extra space is required.
Another Approach:
- Sort the input array in non-decreasing order. We can use any sorting algorithm like quicksort, heapsort, or mergesort to do this.
- Check if the value of K is greater than or equal to the length of the array. If it is, then we can simply return the last element of the sorted array as this would be the maximum possible value that can be achieved after applying K operations.
- If the value of K is less than the length of the array, then we need to determine the maximum value that can be achieved by applying K operations.
- We can achieve this by repeatedly swapping adjacent elements that are
C++
// C++ code to implement the approach.#include <bits/stdc++.h>using namespace std;int main() {int N = 6, K = 3 ;int arr[] = { 9, 1, 3, 7, 2, 5 } ;// Partial sorting the array up to the Kth elementnth_element(arr, arr+K, arr+N);// Condition when K is greater than// or equal to length of arr[] then// returning element at last// index of arr[]if( K >= N ) cout << arr[ N-1 ] ;// if K is less than length of// arr[] then returning element at Xth positionelse cout << arr[ K ] ;return 0;} |
Java
import java.util.Arrays;public class Main { public static void main(String[] args) { int N = 6, K = 3; int[] arr = { 9, 1, 3, 7, 2, 5 }; // Partial sorting the array up to the Kth element Arrays.sort(arr); // Condition when K is greater than // or equal to the length of arr[], then // returning the element at the last // index of arr[] if (K >= N) { System.out.println(arr[N - 1]); } // if K is less than the length of // arr[] then returning the element at the Kth // position else { System.out.println(arr[K]); } }} |
Python3
# python3 code to implement the approach.if __name__ == "__main__": N = 6 K = 3 arr = [9, 1, 3, 7, 2, 5] # Partial sorting the array up to the Kth element arr.sort() # Condition when K is greater than # or equal to length of arr[] then # returning element at last # index of arr[] if(K >= N): print(arr[N-1]) # if K is less than length of # arr[] then returning element at Xth position else: print(arr[K]) # This code is contributed by Prajwal Kandekar |
C#
using System;public class Program { public static void Main() { int N = 6, K = 3; int[] arr = { 9, 1, 3, 7, 2, 5 }; // Partial sorting the array up to the Kth element Array.Sort(arr); // Condition when K is greater than // or equal to the length of arr[] then // returning the element at the last // index of arr[] if (K >= N) { Console.WriteLine(arr[N - 1]); } // if K is less than the length of // arr[] then returning the element at the Kth // position else { Console.WriteLine(arr[K]); } }} |
Javascript
// JS code to implement the approach.let N = 6, K = 3 ;let arr = [ 9, 1, 3, 7, 2, 5 ];// Partial sorting the array up to the Kth elementarr.sort((a, b) => a - b);// Condition when K is greater than// or equal to length of arr[] then// returning element at last// index of arr[]if( K >= N ) console.log(arr[ N-1 ]) ;// if K is less than length of// arr[] then returning element at Xth positionelse console.log(arr[ K ]) ; |
5
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
