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
Explanation: Sum of arr[2] + arr[4]Input: N = 8, K = 4, arr[] = {11, 31, 17, 18, 37, 14, 15, 11}
Output: 0
Explanation: 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++
// C++ program to implement the idea:#include <bits/stdc++.h>using namespace std;// Function to minimize cost to bring max at Kth// position by swappingint minimizeCost(int arr[], int N, int K){ // Store maximum element in array 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];}// Driver Codeint main(){ int N = 6; int k = 4; int arr[N] = { 3, 7, 8, 7, 4, 5 }; cout << minimizeCost(arr, N, k); return 0;} |
Java
// Java program to implement the idea:import java.io.*;import java.util.*;class GFG { // Function to minimize cost to bring max at Kth // position by swapping public static int minimizeCost(int[] arr, int N, int K) { // Store maximum element in array int max_element = Integer.MIN_VALUE; 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 int temp = arr[K]; arr[K] = arr[idx]; arr[idx] = temp; return arr[K] + arr[idx]; } // Driver Code public static void main(String[] args) { int N = 6; int k = 4; int[] arr = { 3, 7, 8, 7, 4, 5 }; System.out.println(minimizeCost(arr, N, k)); }}// This code is contributed by Ishan Khandelwal |
Python3
# Python3 program to implement the idea:# Function to minimize cost to bring max at Kth# position by swappingimport sysdef minimizeCost(arr, N, K): # Store maximum element in array max_element = -sys.maxsize -1 idx = -1 for i in range(N): if (max_element < arr[i]): max_element = arr[i] idx = i if (idx == K): return 0 arr[K], arr[idx] = arr[idx],arr[K] return arr[K] + arr[idx]# Driver CodeN = 6k = 4arr = [ 3, 7, 8, 7, 4, 5 ]print(minimizeCost(arr, N, k))# This code is contributed by shinjanpatra |
C#
// C# program to implement the idea:using System;public class GFG { // Function to minimize cost to bring max at Kth // position by swapping public static int minimizeCost(int[] arr, int N, int K) { // Store maximum element in array int max_element = int.MinValue; 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 int temp = arr[K]; arr[K] = arr[idx]; arr[idx] = temp; return arr[K] + arr[idx]; } // Driver Code public static void Main(string[] args) { int N = 6; int k = 4; int[] arr = { 3, 7, 8, 7, 4, 5 }; Console.WriteLine(minimizeCost(arr, N, k)); }}// This code is contributed by AnkThon |
Javascript
<script> // JavaScript code for the above approach // Function to minimize cost to bring max at Kth // position by swapping function minimizeCost(arr, N, K) { // Store maximum element in array let max_element = Number.MIN_VALUE; let idx = -1; for (let i = 0; i < N; i++) { if (max_element < arr[i]) { max_element = arr[i]; idx = i; } } if (idx == K) return 0; let temp = arr[k]; arr[k] = arr[idx]; arr[idx] = temp; return arr[K] + arr[idx]; } // Driver Code let N = 6; let k = 4; let arr = [3, 7, 8, 7, 4, 5]; document.write(minimizeCost(arr, N, k)); // This code is contributed by Potta Lokesh </script> |
12
Time Complexity:- O(N)
Auxiliary Space:- O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!