Given an array of n integers, we can remove one element of the array by the following operation.
Operation:We select any two numbers of the array and remove the larger number, Cost including in this operation is equal to the smaller number.
You have to reduce the array into a single element by performing above operations with minimum cost.
Examples:
Input : arr[] = {3 4}
Output : 3
We remove 4 by picking both elements and paying cost equal to smaller.Input : 4 2 5
Output : 4
We first pick 4, 2, remove 4 by paying cost 2. Then we remove 5 by again paying cost 2.
As we have to reduce the array to a single element, and it is given that if we select any two numbers, then the cost of removing the larger is equal to the smaller number. So to minimize the total cost, we always take the smallest number with other numbers to remove that.so total cost will be (n-1)*smallest number.
Implementation:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// this function returns the minimum// cost of the arrayint getMinCost(int arr[], int n){ int min_ele = *min_element(arr, arr+n); return min_ele * (n - 1);}int main(){ int arr[] = { 4, 2, 5 }; int n = sizeof(arr)/sizeof(arr[0]); cout << getMinCost(arr, n) << endl; return 0;} |
Java
// Java Program for the above approachimport java.util.Collections;import java.util.Arrays;public class GfG { // This function returns the minimum // cost of the array public static int getMinCost(Integer arr[], int n) { int min_ele = Collections.min(Arrays.asList(arr)); return min_ele * (n - 1); } // Driver code public static void main(String []args){ Integer[] arr = { 4, 2, 5 }; int n = arr.length; System.out.println(getMinCost(arr, n)); }}// This code is contributed by Rituraj Jain |
Python3
# Python3 Program for the above approach# Function returns the minimum # cost of the array def getMinCost(arr, n): min_ele = min(arr) return min_ele * (n - 1)# Driver Codearr = [4, 2, 5]n = len(arr)print(getMinCost(arr, n))# This code is contributed # by Shrikant13 |
C#
// C# Program for the above approachusing System;using System.Linq;class GfG { // This function returns the minimum // cost of the array public static int getMinCost(int []arr, int n) { int min_ele = arr.Min(); return min_ele * (n - 1); } // Driver code public static void Main(String []args) { int[] arr = { 4, 2, 5 }; int n = arr.Length; Console.WriteLine(getMinCost(arr, n)); }}// This code contributed by Rajput-Ji |
PHP
<?php// PHP Program for the above approach// this function returns the minimum // cost of the array function getMinCost($arr, $n) { $min_ele = min($arr); return $min_ele * ($n - 1); } // Code driven $arr =array (4, 2, 5 ); $n = sizeof($arr)/sizeof($arr[0]); echo getMinCost($arr, $n); #This code contributed by ajit?> |
Javascript
<script> // Javascript Program for the above approach // This function returns the minimum // cost of the array function getMinCost(arr, n) { let min_ele = Number.MAX_VALUE; for(let i = 0; i < n; i++) { min_ele = Math.min(min_ele, arr[i]); } return min_ele * (n - 1); } let arr = [ 4, 2, 5 ]; let n = arr.length; document.write(getMinCost(arr, n)); </script> |
4
Complexity Analysis:
- Time Complexity: O(n), since the min_element function takes linear time to return the minimum element.
- Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!