Monday, June 27, 2022
HomeSoftware DevelopmentDecrease price to carry most ingredient at Kth place by swapping

# Decrease price to carry most ingredient at Kth place by swapping

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 + arr

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

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 ` `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)

RELATED ARTICLES