Maximize the minimum Array value by changing elements with adjacent K times

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 arr[] in one operation 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: 7

Input: 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:  5

When 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:

Java

  

import java.util.*;

  

class GFG {

  

    

    public static void main(String[] args)

    {

        int N = 6, X = 3;

        int[] arr = { 9, 7, 3, 1, 2, 5 };

  

        

        System.out.println(Min_Value(N, X, arr));

    }

  

    

    static int Min_Value(int N, int X, int arr[])

    {

        

        

        Arrays.sort(arr);

  

        

        

        

        

        if (X == arr.length || X > arr.length)

            return (arr[arr.length - 1]);

  

        

        

        

        else

            return (arr[X]);

    }

}

Time Complexity: O(N * logN), because sorting is performed.
Auxiliary Space: O(1), as no extra space is required.

Kashish Kumar

Source link