Minimize cost to bring maximum element at Kth position by swapping

Improve Article

Save Article

Like Article

Given two integers N and K and an array of N positive integers (i.e., a0, a1, a2…., an-1), the task is to find the minimum cost to bring maximum value to Kth position by swapping (1-based indexing). The cost of swapping the elements is defined as the sum of values of swapping elements.

Example:

Input: N = 6, K = 4, arr[] = {3, 7, 8, 7, 4, 5}
Output: 12
Explaination: Sum of arr[2] + arr[4]

Input: N = 8, K = 4, arr[] = {11, 31, 17, 18, 37, 14, 15, 11}
Output: 0
Explaination: Maximum is already at arr[4]

Approach:
The idea is to find the position of the maximum element if the maximum element is not at Kth position then swap it with the element which is at Kth position and the answer will be the cost of the swapping element which is the sum values of swapping elements. if the maximum element is at kth position then the answer will be 0.

Follow the steps below to implement the above idea:

  • Find the position of the maximum element.
  • Check if the maximum element is at Kth position 
    • If true, then return 0.
    • Otherwise, swap the maximum element with the element at Kth position and return the sum of values of swapping elements.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

  

int minimizeCost(int arr[], int N, int K)

{

  

    

    int max_element = INT_MIN;

    int idx = -1;

  

    for (int i = 0; i < N; i++) {

        if (max_element < arr[i]) {

            max_element = arr[i];

            idx = i;

        }

    }

  

    if (idx == K)

        return 0;

  

    swap(arr[K], arr[idx]);

    return arr[K] + arr[idx];

}

  

int main()

{

    int N = 6;

    int k = 4;

    int arr[N] = { 3, 7, 8, 7, 4, 5 };

  

    cout << minimizeCost(arr, N, k);

  

    return 0;

}

Time Complexity:- O(N)
Auxiliary Space:- O(1)

By Julio MarchiPosted on